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

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

Проведя оптимизацию префикс-функции (подробнее здесь ), получим итоговый алгоритм с асимптотикой O(n):

vector<int> prefix_function (string s) {
	int n = (int) s.length();
	vector<int> pi (n);
	for (int i=1; i<n; ++i) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])  ++j;
		pi[i] = j;
	}
	return pi;
}

Task
Time limit: 1000 ms,
Memory limit: 256 Mb

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

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

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

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

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

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

Одна строка длины N, 0 < N ≤ 10⁶, состоящая из маленьких латинских букв.

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

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

Ввод	Вывод
abracadabra	0 0 0 1 0 1 0 1 2 3 4

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!

Attach the program source file:
or enter the source code in the language:

Rules for designing programs and a list of errors during automatic task verification

Results:

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

Education

My Account

About us

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

№ 2/10 Префикс-функция

Education

My Account

About us