Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
57 lines (44 sloc) 1.24 KB
/*************************************************************************************
Prefix function. O(N)
About it: http://e-maxx.ru/algo/prefix_function
Based on problem 1323 from informatics.mccme.ru:
http://informatics.mccme.ru/mod/statements/view3.php?id=241&chapterid=1323
*************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 1000100;
int n;
string s;
int p[MAXN];
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
getline(cin, s);
n = (int) s.length();
for (int i = 2; i <= n; i++) {
int prev = p[i - 1];
while (prev > 0 && s[prev] != s[i - 1])
prev = p[prev];
if (s[prev] == s[i - 1])
prev++;
p[i] = prev;
}
for (int i = 1; i <= n; i++)
printf("%d ", p[i]);
return 0;
}