Подпись

В силу небольших ограничений на длину строк мы можем перебрать всевозможные варианты соединений, которые могут быть получены из данных имен. Сделаем это следующим образом: будем убирать по одному символу справа из первого имени и приписывать к нему второе, при этом каждый раз будем проверять: имеется ли в образующейся таким образом строке первое имя в качестве подстроки, если это так, то данная строка удовлетворяет необходимому условию (заканчиваться она будет вторым именем по построению), останется только преобразовать первую букву первого имени в заглавную (следует помнить, что может быть несколько вариантов вхождения первой строки в получившуюся). При встрече очередной строки, начинающейся и заканчивающейся нашими именами, будем сравнивать ее с ранее найденной, на текущий момент самой короткой. Если текущая окажется более подходящей (короче или в случае равенства длины лексикографически меньше), то ее следует запомнить. После перебора всех вариантов сокращения первой строки следует поменять строки местами, для чего удобно описать отдельную функцию search(a,b) , которая будет сокращать первую строку, приписывая вторую. Следует так же отметить, что в процессе сравнения нужно преобразовывать все символы либо в верхний, либо в нижний регистр. В начале в качестве самой короткой строки можно считать строку, состоящую из суммы исходных имен, которая очевидно обладает необходимым свойством. По завершению поиска в качестве ответа просто останется вывести ту строку, в которой мы хранили текущий наикратчайший вариант.

Алгоритмическая реализация вышеописанной идеи:

  void search(a,b){
    as = lower(a)
    bs = lower(b) 
    for i=0..len(a){
      ss = as[1..i]+bs
      k = 1
      while(k < 3 and (k = ss.find(as,k)) > 0){
        s=ss
        s[i] = upper(s[i])
        s[k] = upper(s[k])
        if(len(s) < len(m) or len(s)==len(m) and s < m) m = s
        k++
      }
    }
  }

  read(a,b)
  m=a+b
  search(a,b)
  search(b,a)
  write(m)

[Обсуждение] [Все попытки] [Задача]