Question

Дана строка-шаблон t и n символьных строк si (|si
| = |t|). Для каждого k от 0 до |t| выведите
ответ на вопрос:
• если мы заменим не более k символов в строке-шаблоне t на «?», чему будет равно количество
строк si
, подходящих под этот шаблон?
Строка si подходит под шаблон t, если на всех позициях, где в t стоит буква, такая же буква
стоит в si
. На позициях, где в t стоит «?», в si может стоять любая буква.
Формат входных данных
В первой строке ввода содержится символьная строка t (1 6 |t| 6 16), состоящая из строчных
букв латинского алфавита и символов «?».
Во второй строке содержится одно целое число n (1 6 n 6 2 · 105
) — количество строк si
.
В следующих n строках ввода содержатся символьные строки si (|si
| = |t|), состоящие из строчных букв латинского алфавита.
Формат выходных данных
В единственной строке выведите |t| + 1 число — ответ для всех k (0 6 k 6 |t|).

Answer 1

Дана строка-шаблон t и n символьных строк si (|si

| = |t|). Для каждого k от 0 до |t| выведите

ответ на вопрос:

• если мы заменим не более k символов в строке-шаблоне t на «?», чему будет равно количество

строк si

, подходящих под этот шаблон?

Строка si подходит под шаблон t, если на всех позициях, где в t стоит буква, такая же буква

стоит в si

. На позициях, где в t стоит «?», в si может стоять любая буква.

Формат входных данных

В первой строке ввода содержится символьная строка t (1 6 |t| 6 16), состоящая из строчных

букв латинского алфавита и символов «?».

Во второй строке содержится одно целое число n (1 6 n 6 2 · 105

) — количество строк si

.

В следующих n строках ввода содержатся символьные строки si (|si

| = |t|), состоящие из строчных букв латинского алфавита.

Формат выходных данных

В единственной строке выведите |t| + 1 число — ответ для всех k (0 6 k 6 |t|).

t = input()

n = int(input())

dp = [[[0 for _ in range(26)] for _ in range(26)] for _ in range(len(t) + 1)]

for j in range(26):

   dp[0][j][j] = n

for k in range(1, len(t) + 1):

   for i in range(1, k + 1):

       for j in range(26):

           if t[k - 1] != '?' and ord(t[k - 1]) != ord('a') + j:

               continue

           for l in range(26):

               dp[k][j][l] += dp[k - 1][j][l]

           if t[k - 1] == '?':

               for j2 in range(26):

                   dp[k][j][j2] += dp[k - 1][j2][l]

ans = []

for i in range(len(t) + 1):

   cnt = 0

   for j in range(26):

       for l in range(26):

           cnt += dp[len(t)][j][l] if i >= len(t) or t[i] == '?' or j == ord(t[i]) - ord('a') else 0

   ans.append(cnt)

print(*ans)