Пошук Конкатенованих Рядків#5792
Обсяг інформації у Всесвітній павутині зростає надзвичайно швидко. У цю епоху інформаційного вибуху ми повинні вміти знаходити лише ті веб-сторінки, які містять інформацію, релевантну нашим потребам. Однією з ключових технологій для цього є пошук за ключовими словами. Використовуючи відомі пошукові системи, ми можемо легко отримати доступ до сторінок, що містять корисну інформацію про тему, яка нас цікавить.
Існує багато варіацій задач пошуку за ключовими словами. Якщо в тексті шукається один рядок, задача досить проста. Але якщо шаблон для пошуку складається з кількох рядків або заданий за допомогою потужної нотації, такої як регулярні вирази, завдання стає складнішим і вимагає ефективних алгоритмів.
У нашій задачі задано кілька рядків (елементні рядки), але вони не шукаються безпосередньо. Цілями пошуку є всі можливі конкатенації елементних рядків у будь-якому порядку.
Наприклад, розглянемо три елементні рядки: aa, b і ccc. У цьому випадку наступні шість конкатенованих рядків є цілями пошуку, тобто вони повинні бути знайдені в тексті:
aabccc
aacccb
baaccc
bcccaa
cccaab
cccbaa
Текст може містити кілька входжень цих рядків. Вам потрібно підрахувати кількість входжень цих рядків, або, точніше кажучи, кількість позицій входжень у тексті.
Два або більше конкатенованих рядків можуть бути ідентичними. У таких випадках необхідно враховувати тонкі аспекти наведеного вище формулювання задачі. Наприклад, якщо два елементні рядки є x і xx, рядок xxx є входженням як конкатенації x і xx, так і xx і x. Оскільки повинна бути підрахована кількість позицій входжень, цей випадок рахується як один, а не два.
Два входження можуть перекриватися. Наприклад, рядок xxxx має входження конкатенації xxx у двох різних позиціях. Цей випадок рахується як два.
Вхід складається з кількох наборів даних, кожен з яких надає набір елементних рядків і текст. Формат набору даних такий.
e_1
e_2
...
e_n
t_1
t_2
...
t_m
Перша строка містить два цілі числа, розділені пробілом. — це кількість елементних рядків. — це кількість рядків, використаних для представлення тексту. знаходиться в межах від до включно.
Кожна з наступних строк надає елементний рядок. Довжина (кількість символів) елементного рядка знаходиться в межах від до включно.
Останні строк у цілому дають текст. Оскільки небажано мати дуже довгу строку, текст розділений на строк новими рядками, але ці нові рядки слід ігнорувати. Вони не є частинами тексту. Довжина кожної з цих строк (не включаючи новий рядок) знаходиться в межах від до включно. Довжина тексту знаходиться в межах від до включно.
Елементні рядки і текст не містять символів, окрім малих літер.
Кінець введення вказується строкою, що містить два нулі, розділені пробілом.
УВАГА! Хоча приклад введення містить лише невеликі набори даних, зауважте, що значно більше, ніж 2^{31}.
Для кожного набору даних у введенні слід вивести одну строку, що містить кількість знайдених позицій. Строка виводу не повинна містити зайвих символів.
Приклад 1