Решение задачи №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