http://acm.pku.edu.cn/JudgeOnline/problem?id=1194
Задача: Скрытые коды
Дано множество кодовых слов и текст. Предложенный текст содержит сообщение, созданное из кодовых слов, включенных в текст некоторым, возможно неоднозначным способом.
Кодовые слова и текст содержат только большие и малые (прописные и строчные) буквы английского алфавита. Большая и малая буквы считаются различными. Длина кодового слова определяется обычным способом: например, длина кодового слова ALL равна 3.
Буквы кодового слова встречаются в данном слове не обязательно последовательно. Например, кодовое слово ALL будет всегда присутствовать в тексте, содержащем последовательность вида AuLvL, где u и v являются последовательностями букв (возможно пустыми). Будем говорить, что AuLvL является покрывающей последовательностью для ALL. В общем случае покрывающая последовательность для кодового слова определяется как подпоследовательность текста, в которой первая и последняя буквы совпадают, соответственно, с первой и последними буквами кодового слова и существует способ восстановить кодовое слово удалением, если необходимо, некоторых букв подпоследовательности. Заметим, что кодовое слово может содержаться в одной или нескольких покрывающих последовательностях или может не встречаться в тексте вообще. Кроме того, покрывающая последовательность может являться покрывающей последовательностью для более чем одного кодового слова.
Покрывающая последовательность определяется своей начальной и конечной позициями в тексте (позициями первой и последней букв, соответственно). Первая буква текста находиться в позиции 1. Будем говорить, что покрывающие последовательности с1 и с2 не перекрываются, если начальная позиция с1 больше (>), чем конечная позиция с2, или наоборот. В противном случае назовем эти две последовательности перекрывающимися.
Решение задачи заключается в извлечении скрытого сообщения из текста. Решение есть множество элементов, каждый из которых состоит их кодового слова и покрывающей последовательности для этого кодового слова. При этом должны соблюдаться следующие условия:
- покрывающие последовательности не перекрывают друг друга;
- длина покрывающей последовательности не превышает 1000;
- сумма длин кодовых слов максимальна (каждый элемент добавляет длину кодового слова, которое он содержит, к сумме длин).
1 <= N <= 100, где N - количество слов.
Максимальная длина кодового слова - 100 букв.
Длина заданного текста не менее 1 и не более 100000 букв.
Будем говорить, что покрывающая последовательность с для кодового слова w является минимальной справа, если никакой собственный префикс с (собственным префиксом с является любая подпоследовательность с такая, что она не равна с) не является покрывающей последовательностью для w. Например, для кодового слова ALL AAALAL является минимальной справа покрывающей последовательностью, в то время как AAALALAL также является покрывающей последовательностью, но не является минимальной справа.
Гарантируется, что в данном тексте:
- для любой позиции в тексте количество минимальных справа покрывающих последовательностей, содержащих эту позицию, не превышает 2500;
- количество минимальных справа покрывающих последовательностей не превышает 10000.
Входные данные
Первая строка входных данных содержит значение N. Каждая из последующих N строк содержит кодовое слово, которое является последовательностью букв без пробелов между ними. Каждое слово однозначно определено своим порядковым номером в списке: целые числа от 1 до N являются номерами кодовых слов. В последней строке входных данных задано последовательность букв, заканчивающейся одним символом строки (end-of-line character), за которым следует символ конца файла (end-of-file symbol).
Выходные данные
В единственной строке выведите сумму, которая вычислила ваша программа.
Пример входных данных:
4
RuN
RaBbit
HoBbit
StoP
StXRuYNvRuHoaBbvizXztNwRRuuNNP
Пример выходных данных:
12
Обсуждение задачи