Z-функция. Префикс-функция

Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.

 

Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).

 

Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.

 

Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).

 

Требуется для всех i от 1 до N вычислить \(\pi[i]\).

 

Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.

 

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

 

Примеры

№	Входные данные	Выходные данные
1	abracadabra	0 0 0 1 0 1 0 1 2 3 4

#include <bits/stdc++.h>
main()
{
    std::string s;
    std::cin >> s;
    int n = s.size(), p[50003], j, i = 1;
    for (; i < n; i++)
    {
        j = p[i - 1];
        for (; j && s[i] != s[j]; j = p[j - 1]);
        p[i] = (s[i] == s[j] ? ++j : j);
    }
    std::cout << n - p[n - 1];
}

Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

Выходные данные

Вывести k строк с ответами на запросы.

Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S. 

Входные данные

В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).

Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

Выходные данные

В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.