1455 timus

Что имелось ввиду под решениям с хешами не знаю. Ради интереса только что сдал ее. Хеши в этом решении можно использовать для проверки совпадения суффикса одного слова и префикса другого, хотя и за О(Н) оно проходит за 0.031.

Будем одновременно строить 2 строки из разных слов, которые в итоге должны совпасть. Очевидно, что самые первые слова в каждой из строк должны отличаться. Затем, когда мы их поставили у нас останется незакрытым суффикс одного из слов. Это наталкивает на мысль о динамике по номеру слова и длине незакрытого суффикса.

Чтобы проверить, можно ли из данного состояния динамики закончить строки так чтобы они стали одинаковыми, будем пытаться к более короткой строке приписать какое-то слово, префикс которого совпадает с оставшимся суффиксом (в случае, если слово короче суффикса, то оно должно являться его префиксом). Тогда существует три варианта:

1. Наше слово короче чем оставшийся суффикс. Тогда мы просто переходим к состоянию, где в более длинной строке последнее слово то же самое, но незакрытый суффикс короче.
2. Наше слово длиннее чем оставшийся суффикс. Тогда у нас меняется самая длинная строка, а следовательно, меняется и номер последнего слова в самой длинной строке. Длину незакрытого суффикса вычислить легко, зная длину слова.
3. Наше слово равняется оставшемуся суффиксу. В этом случае у нас строки совпадают и мы получили наш ответ.

Правда чтобы строка, которая получается таким образом была не длиннее 20000 символов, пришлось отсортировать словарь по длине.

KADR, а как ты реализовал эту идею? Я написал БФС по состояниям получаю ВА6 или ВА8.

Я думаю, что я написал описано идея, но она получает WA8. Может ли кто мне помочь.