Объясните мне кратко ход решения (код писать не нужно). с информатикса, номер - 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. читаем слова из словаря, для каждого слова находим все , вставляем их в multimap в качестве ключа, значение можно ставить любое (например, (int) 1). после этого в цикле читаем слова-образцы и выводим значение count от каждого слова-образца.  программа будет иметь примерно такую структуру: multimap< string, > subprefixes input n n times:     input s     for j = 0..size of s:         if s[..j] is subprefix of s:             subprefixes.insert(pair< string, > (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() - как можно ускорить всё это? 1) выберем какое-нибудь достаточно большое (по сравнению с символов)  простое число x, например, x = 1009. вычислим для строки s все хеши по формуле   для n = 1..len s  (это делается за линейное время относительно len s, если предпросчитать все степени x от нулевой до 50) теперь если у строки s длины k есть длины j, то обязательно  – проверить это быстрее, чем ходить циклом. 2) необязательно хранить в multimap-е подстроки, это дорого и по времени и по памяти. можно хранить хеши. 3) можно вместо одного multimap-а создать 50 multimap-ов, в каждом хранить только одной длины. получаем примерно такое: pow = new long long[51] pow[0] = 1 for i = 1..50:     pow[i] = x * pow[i - 1] suprefixes = new multimap< long long, > [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.

переселение комбинации