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

   Обсуждение задачи