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

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

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

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

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

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

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

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


    #include<iostream>

#include<string>

#include<vector>

using namespace std;

vector<int> pf(string s)

	{

	int i,j,n=s.size();

	vector<int>pi(n);

	for(i=1;i<n;++i)

		{

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

int main()

{

	string s;

	cin>>s;

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

	return 0;}

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