Поиск конкатенированных строк
Количество информации в Интернете растет стремительно. В эпоху информационного взрыва мы должны уметь находить только те веб-страницы, которые содержат информацию, соответствующую нашим нуждам. Одной из ключевых технологий для этого является поиск по ключевым словам. Используя известные поисковые системы, мы можем легко находить страницы с полезной информацией по интересующей нас теме.
Существует множество вариаций задач поиска по ключевым словам. Если в заданном тексте ищется одна строка, задача довольно проста. Если же шаблон для поиска состоит из нескольких строк или задан с помощью сложной нотации, такой как регулярные выражения, задача требует более сложных алгоритмов для эффективного выполнения.
В нашей задаче дано несколько строк (элементные строки), но они не ищутся напрямую. Конкатенации всех элементных строк в любом порядке являются целями поиска.
Например, рассмотрим три элементные строки: aa, b и ccc. В этом случае следующие шесть конкатенированных строк являются целями поиска и должны быть найдены в тексте:
aabccc
aacccb
baaccc
bcccaa
cccaab
cccbaa
Текст может содержать несколько вхождений этих строк. Вам нужно подсчитать количество вхождений этих строк, или, точнее, количество позиций вхождений в тексте.
Две или более конкатенированных строки могут быть идентичными. В таких случаях необходимо учитывать тонкости условия задачи. Например, если две элементные строки x и xx, строка xxx является вхождением как конкатенации x и xx, так и xx и x. Поскольку должно быть подсчитано количество позиций вхождений, этот случай считается как одно, а не два.
Два вхождения могут перекрываться. Например, строка xxxx имеет вхождения конкатенации xxx в двух разных позициях. Этот случай считается как два.
Входные данные
Входные данные состоят из нескольких наборов данных, каждый из которых содержит набор элементных строк и текст. Формат набора данных следующий:
n m
e_1
e_2
...
e_n
t_1
t_2
...
t_m
Первая строка содержит два целых числа, разделенных пробелом. n — это количество элементных строк. m — это количество строк, используемых для представления текста. n находится в диапазоне от 1 до 12 включительно.
Каждая из следующих n строк содержит элементную строку. Длина (количество символов) элементной строки находится в диапазоне от 1 до 20 включительно.
Последние m строк в совокупности составляют текст. Поскольку нежелательно иметь очень длинную строку, текст разделен на m строк с помощью символов новой строки, но эти символы новой строки следует игнорировать. Они не являются частью текста. Длина каждой из этих строк (не включая символ новой строки) находится в диапазоне от 1 до 100 включительно. Длина текста находится в диапазоне от 1 до 5000 включительно.
Элементные строки и текст не содержат символов, кроме строчных букв.
Конец ввода обозначается строкой, содержащей два нуля, разделенных пробелом.
ВНИМАНИЕ! Хотя пример ввода содержит только небольшие наборы данных, обратите внимание, что 12! × 5000 значительно больше, чем 2^31.
Выходные данные
Для каждого набора данных во входных данных должна быть выведена одна строка, содержащая количество совпавших позиций. Строка вывода не должна содержать лишних символов.