Задача 8 регионального этапа Всероссийской олимпиады школьников по информатике 2011/2012 учебного года (offline)

Задачу добавил: alef

Успешно сдано решений: 24

«Abracadabra»

Входной файл:  input.txt
Выходной файл:  output.txt
Ограничение по времени:    2 секунды
Ограничение по памяти:    256 мегабайт

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.
В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t₁, t₂, …, t_n и набор из
m строк-образцов s₁, s₂, …, s_m. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.
Требуется написать программу, которая по заданному числу n, n словам словаря
t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец  является супрефиксом.

Формат входного файла

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).
Последующие n строк содержат слова t₁, t₂, …, t_n, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 10⁶. Словарь не содержит пустых слов.
Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).
Последующие m строк содержат строки-образцы s₁, s₂, …, s_m, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 10⁶. Никакая строка-образец не является пустой строкой.

Формат выходного файла

Выходной файл должен содержать m чисел, по одному на строке.
Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Пример входного файла
4
abacaba
abracadabra
aa
abra
3
a
abra
abac  

Пример выходного файла
4
2
0

Система оценивания
Правильные решения для тестов, в которых 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, будут оцениваться из 30 баллов.

Сдать задачу

Задать вопрос жюри по этой задаче