| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 12620 | Accepted: 6198 |
Description
from such boring job, the innovative little cat works out an easy but fantastic algorithm:
Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).
Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings
of S? (He might thank you by giving your baby a name:)
Input
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
Sample Input
ababcababababcabab aaaaa
Sample Output
2 4 9 18 1 2 3 4 5
KMP 算法next数组的应用， 寻找所有可能的公共前后缀，我们先对整个串求一个next数组，（未优化的next数组相当于每个字符之前存在的最长的公共前后缀长度-1）
然后去“截”这个串，每次截的位置是next[len - 1]，len是未截之前字符串长度，一开始为整个字符串长度
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 400010;
char str[N];
int next[N];
int ans[N];
void get_next()
{
int len = strlen(str);
int j = 0, k = -1;
next[0] = -1;
while (j < len - 1)
{
if (k == - 1 || str[j] == str[k])
{
++k;
++j;
next[j] = k; //没有优化过的
// 优化
/*if (str[k] != str[j])
{
next[j] = k;
}
else
{
next[j] = next[k];
}*/
}
else
{
k = next[k];
}
}
}
int main()
{
while (~scanf("%s", str))
{
int cnt = 0;
int len_len = strlen(str);
str[len_len++] = '*';
str[len_len] = '\0';
int len = len_len;
get_next();
while(1)
{
if (next[len_len - 1] > 0)
{
ans[++cnt] = next[len_len - 1];
// for (int i = 0; i < next[len_len - 1]; ++i)
// {
// printf("%c", str[i]);
// }
// printf("\n");
len_len = next[len_len - 1] + 1;
continue;
}
break;
}
for (int i = cnt; i >= 1; --i)
{
printf("%d ", ans[i]);
}
printf("%d\n", len - 1);
}
return 0;
}