Растолкуйте мне кратко ход решения задачи (код писать не необходимо). Задачка
Растолкуйте мне коротко ход решения задачи (код писать не нужно). Задачка с информатикса, номер - 3871.
Строчка s именуется супрефиксом для строчки t, если t начинается с s и заканчивается на s. К примеру, abra является супрефиксом для строки abracadabra. В частности, сама строчка t является своим супрефиксом. Супрефиксы играют важную роль в разных методах на строчках.
В этой задачке нужно решить оборотную задачку о поиске супрефикса, которая заключается в последующем. Задан словарь, содержащий n слов t1, t2, , tn и набор из m строк-образцов s1, s2, , sm. Необходимо для каждой строчки-образчика из данного комплекта отыскать количество слов в словаре, для которых эта строчка-эталон является супрефиксом.
Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, , tn, данному числу m и m строчкам-образчикам s1, s2, , sm вычислит для каждой строчки-образца количество слов из словаря, для которых эта строчка-эталон является супрефиксом.
Входные данные
Первая строка входного файла содержит целое число n (1 n 200 000).
Последующие n строк содержат слова t1, t2, , tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превосходит 50. Суммарная длина всех слов не превосходит 106. Словарь не содержит пустопорожних слов.
Потом следует строчка, содержащая целое число m (1 m 200 000).
Следующие m строк содержат строчки-эталоны s1, s2, , sm, по одной на каждой строке. Любая строчка-эталон состоит из строчных букв латинского алфавита: Длина каждой строчки-образчика не превышает 50. Суммарная длина всех строк-образчиков не превышает 106. Никакая строка-эталон не является пустопорожней строкой.
Выходные данные
Выходной файл должен содержать m чисел, по одному на строке.
Для каждой строчки-образчика в порядке, в котором они заданы во входном файле, следу.т вывести количество слов словаря, для которых она является супрефиксом.
Образцы
входные данные
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
выходные данные
4
2
0
Решать надобно через multimap(!).
Программка будет иметь приблизительно такую структуру:
multimaplt;string, ...gt; subprefixes
input n
n times:
input s
for j = 0..size of s:
if s[..j] is subprefix of s:
subprefixes.insert(pairlt;string, ...gt;(s[..j], ...))
input m
m times:
input s
print subprefixes.count(s)
Остался вопрос, как определять, является ли s[..j] супрефиксом. Окончательно, можно это делать легковерно: пройти циклом для всех возможных длин подстрок j и проверить, правда ли, что s[0] = s[s.size() - j - 1], s[1] = s[s.size() - j]...
Как можно ускорить всё это?
1) Выберем какое-нибудь довольно великое (по сопоставлению с кодами символов) обычное число x, например, x = 1009. Вычислим для строчки s все хеши по формуле
Теперь если у строчки s длины k есть супрефикс длины j, то непременно
2) Необязательно беречь в multimap-е подстроки, это недешево и по медли и по памяти. Можно беречь хеши.
3) Можно заместо 1-го multimap-а создать 50 multimap-ов, в каждом хранить только супрефиксы одной длины.
Получаем приблизительно такое:
pow = new long long[51]
pow[0] = 1
for i = 1..50:
pow[i] = x * pow[i - 1]
suprefixes = new multimaplt;long long, ...gt;[51]
input n
n times:
input s
h = hashes(s)
k = len s
for j = 1..k:
if h[j] * pow[k - j] == h[k] - h[k - j - 1]:
suprefixes[j].insert(pair(h[j], ...))
input m
m times:
input s
print puprefixes[len s].count(hash(s))
В принципе, для такового решения multimap не нужен, довольно иметь map, и хранить для каждого ключа количество вхождений. Это можно делать и для multimap.
-
Вопросы ответы
Статьи
Информатика
Статьи
Математика.
Физика.
Математика.
Разные вопросы.
Разные вопросы.
Математика.
Разные вопросы.
Математика.
Физика.
Геометрия.