составить соотвествие по тегам...​

Можно поступить следующим образом: создаем 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() - j]...

Как можно ускорить всё это?
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.

Чтобы упростить программу, будем выводить команды типа "сделай ЕДИНИЦА", где ЕДИНИЦА и ДЕВЯТЬ - процедуры.
Описание процедуры:
процедура <имя процедуры>
нач       
<тело процедуры>
кон

процедура ЕДИНИЦА
нач
поворот шаг шаг шаг шаг
поворот поворот
прыжок прыжок прыжок прыжок
поворот
кон

процедура ДЕВЯТЬ
нач
шаг поворот шаг шаг шаг
шаг поворот шаг поворот шаг
шаг поворот шаг поворот поворот поворот
прыжок прыжок поворот
кон

тело программы: программа Число 1919
     нач
          сделай ЕДИНИЦА
          прыжок
          сделай ДЕВЯТЬ
          прыжок
          сделай ЕДИНИЦА
          прыжок
          сделай ДЕВЯТЬ
    кон