Решение задачи №1161 «Z-функция» с ACMP

Условие задачи

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

Для каждой i-й позиции строки S определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки S. Значением Z-функции Z(i) будем считать длину этого Z-блока. При i=1 будем считать, что Z(1)=0, несмотря на то, что в начале строки строка совпадает сама с собой.

Требуется для всех i от 1 до N вычислить значение Z(i).

Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.

Выходные данные
В выходной файл OUTPUT.TXT выведите все значения Z-функции.

Решение на C++


    #include<iostream>

#include<string>

#include<vector>

using namespace std;

vector<int>dp(string s)

{

	int n=(int)s.size();

	vector<int>z(n);

	for (int i=1,l=0,r=0;i<n;++i)

	{

	if(i<= r)z[i]=min(r-i+1, z[i-l]);

	while(i+z[i]<n&&s[z[i]]==s[i+z[i]])++z[i];

	if(i+z[i]-1>r)l=i,r=i+z[i]-1;

	}

	return z;

}

int main()

{

	string s;

	cin>>s;

	for(auto a:dp(s))cout<<a<<' ';

	return 0;}

Условия задач взяты с сайта acmp.ru