Чайнворд

[RacoonJ]

Журналисты газеты "The Run Times" к каждому номеру готовят чайнворд. Чайнворд - это последовательность клеток, в которые читатель вписывает угаданные слова. При этом каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова "set", "too" и "olymp" следующим образом: "setoolymp".
Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга "soly", который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.
Для экономии места в газете журналисты хотят составить чайнворд минимальной длины.
Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.
Входные данные
В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N - количество слов, которые можно использовать при составлении чайнворда (1 <= N <= 1000). В последующих N строках перечисляются различных слова, каждое из которых содержит от двух до 10 букв.
Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов.
Выходные данные
В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них.
Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ - знак вопроса.
Примеры
chain.in
soly
4
set
olymp
lye
too
chain.out
set
too
olymp
chain.in
solve
4
set
owe
evil
too
chain.out
?
chain.in
solve
7
olymp
set
too
pink
knot
parliament
tvs
chain.out
set
too
olymp
pink
knot
tvs
set
Решение:
Сначала считаем все слова в массив. Теперь нам необходимо создать массив расстояний от буквы до буквы (двумерный t['a'..'z', 'a'..'z'], где каждый элемент содержит длину пути от буквы до буквы, какое слово используется, если в пути одно слово, и через какую букву идет, если в пути более одного слова). Сначала заполним его минимальными длинами слов. То есть, если в списке есть слова too и to, то t['t', 'o'].num = 2
Теперь необходимо найти переходы, в которых участвует несколько слов, для этого удобно воспользоваться алгоритмом Флойда. Примерно так должен выглядеть этот кусок кода:

for c1 := 'a' to 'z' do
for c2 := 'a' to 'z' do
for c3 := 'a' to 'z' do
if (t[c2, c3].num > t[c2, c1].num + t[c1, c3].num
- 1) then begin
t[c2, c3].num := t[c2, c1].num + t[c1, c3].num - 1;
t[c2, c3].aft := c1;
t[c2, c3].add := 0;
end;
Здесь t.num - количество букв на пути, t.aft - через какую букву идет, в случае если идет по цепочке слов и t.add - через какое слово идет (в случае если идет по одному слову). Важно то, что при суммировании длин двух переходов (от c2 до c1 и от c1 до c3) сумма уменьшается на 1 - буква c1 накладывается.
Теперь у нас имеется список кратчайших расстояний и по нему мы можем восстановить кратчайшую последовательность слов.
Кроме этого нам понадобятся две функции, каждая из которых создает массив, в котором для каждого слова хранится количество букв, которые встречаются в образце начиная с позиции k. Т.е. допустим, что мы уже составили последовательность в которой есть k первых букв образца и нам надо определить, сколько последующих букв образца содержит каждое слово. Например, для образца "soly", для которого уже составлена последовательность для 2-х первых букв (k = 2), для слова "olymp" функция должна вернуть значение 2 - в этом слове встречаются буквы "l" и "y". Различие функций состоит в том, что одна из них должна считать количество букв, начиная с первой буквы слова, а другая - со второй. Оба этих массива нам пригодяться впоследствии.
Теперь, собственно, подготовка окончена и начинается решение.
Для решения нам необходим двумерный массив (go[1..250, 'a'..'z'] - каждый элемент хранит: go[i, c].now - сколько букв в строке, содержащей i первых букв образца и заканчивающейся на c; go[k, c].prev - сколько букв образца было в строке до добавления текцщего слова; go[k, c].cpr - какой символ был последний, до добавления текущего слова; go[k, c].pw - номер слова, которое мы добавили; go[k, c].beetw - флаг, использовали ли мы в пути от предыдущего состояния до добавления слова, содержащего буквы образца, другие слова - вместо него можно ставить особую метку в go.cpr - символ не из множества 'a'..'z'). Начнем заполнение этого массива.

[RacoonJ]

Прогоним процедуру генерации массива, в котором содержится количество букв образца в слове, включая первую букву слова, с аргументом 0 - в последовательности еще нет ни одной буквы образца (пусть этот массив называется inw[j], где j - номер слова). Теперь организуем цикл (j) по всем словам и, внутри него, цикл (k) от 1 до inw[j]. Пусть c - последняя буква текущего слова. Если длина слова меньше go[k, c].now (сначала заполним все go.now бесконечностью), то запишем в go[k, c]: now - длина слова, prev = 0 - нет предыдущего слова, beetw или cpr - установим флаг цепочки в false - нет предшествующей цепочки, pw = j - номер слова.
Теперь - основной этап решения.
Заведем цикл (i) от 1 до количества букв в образце - 1. На каждом шаге формируем функциями два массива вхождений букв образца для каждого слова, считая, что i букв образца уже совпали. Пробегаем циклом (c) по всем буквам, на которые оканчивается текущая строка.
Следующие действия выполняем только если существует строка, содержащая i символов образца и оканчивающаяся на c. Организовываем еще один внутренний цикл по словам. Если первая буква текущего слова равна c, т.е. слово начинается на ту букву, на которую кончается текущая последовательность, то организовываем цикл (k) от 1 до количества букв образца, встречающихся в слове j, начиная со второй буквы.
В этом цикле проверяем - если последовательность, содержащая i + k букв образца и оканчивающаяся на последнюю букву слова, не существует или длиннее, чем текущая последовательность go[i, c].num + длина текущего слова (j) - 1, то заменяем ее данные на следующие: now = go[i, c].now + length(w[j]) - 1, prev = i, beetw или cpr = false, pw = j.
Заканчиваем цикл по k и условие что первая буква слова совпадает с последней буквой текущей последовательности (c). Теперь напишем кусок кода для случая, если первая буква текущего слова и последняя буква последовательности не совпадают.
Организуем цикл (k) от 1 до количества букв образца, содержащихся в слове j начиная с первой буквы. Если последовательность, содержащая k + i первых букв образца и заканчивающаяся на последнюю букву слова не определена, или ее длина больше чем, go[i, c] + (длина текущего слова - 1) + (расстояние от последней буквы текущей последовательности (с) до первой буквы слова - 1), то ставим ей в соответствие новые параметры: num = go[i, c] + t[c, w[j, h]] - 1 + h - 1, где h - длина слова, w - массив слов; prev = i; pw = j; cpr = c и beetw = true - содержит перед собой цепочку, которая начинается с буквы c и оканчивается первой буквой слова.
После работы этих циклов проверяем наличие ответа. Организовываем цикл по c от 'a' до 'z' и находим минимальное значение go[q, c].now (сохраним c для минимального значения как cbest, где q - длина заданной последовательности. Если минимум равен бесконечности, то значит не существует ни одного чайнворда из заданных слов, содержащего необходимую последовательность. Выводим "?" и выходим из программы.
Если же ответ существует, то его вывод также требует от нас определенных усилий. Мы знаем cbest и с помощью него восстановим лучшую последовательность. Для этого организуем цикл repeat until (сначала j равно длине данной последовательности, pc = cbest) и будем записывать в массив (por) номера слов go[pj, pc].pw и, в случае наличия флага beetw, также устанавливать флаг. После этого pc1 := go[pj, pc].cpr, pj := go[pj, pc].prev, pc := pc1 - переходим к предыдущему слову, содержащему буквы из данной последовательности.
Массив por необходимо перевернуть - он содержит слова в обратном порядке. Затем начинаем выводить слова. В случае, если установлен флаг, непосредственно перед словом необходимо вывести цепочку, соединяющую предыдущее слово с текущим. Для этого воспользуемся обратным рекурсивным обходом дерева, который восстановит всю цепочку в правильном порядке. Текст этой процедуры будет выглядеть примерно так:

procedure addlist(a, b : char);
begin
if t[a, b].add = 0 then begin
addlist(a, t[a, b].aft);
addlist(t[a, b].aft, b);
end else writeln(w[t[a, b].add]);
end;
Сначала в процедуру addlist в качестве a и b передаются последняя буква предыдущего слова и первая буква текущего соответственно.
Общая максимальная сложность алгоритма получается O(K*H*N*L), где K - количество букв в образце (250), H - мощность алфавита (26), N - количество слов (1000) и L - максимальная длина слова (10). Для самого худшего (практически нереализуемо) получаем порядка 65 000 000 операций, что вполне приемлемо для современных компьютеров.

[Аватар]

Отчет об успехах?

[RacoonJ]

Сообщение от Аватар

Отчет об успехах?

ахаха
нет
это задание с объяснением
однако,объяснение не особо помогает)

[WinCoder]

>> это задание
Кому?

[zvygin1964]

Как кому? Напрямую же написано:

Сообщение от RacoonJ

Журналисты газеты "The Run Times"