Решение задачи Z-функция с Acmp

Без пояснения   Просмотров: 12



Код


    #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;}   
        

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться