Seek the Name, Seek the Fame
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 17581 | Accepted: 9019 |
Description
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape 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:)
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
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.
Sample Input
ababcababababcabab aaaaa
Sample Output
2 4 9 18 1 2 3 4 5
题解：
题目的意思是说给你一个串，问有多少完全相同的前后缀，只输出这样的串的长度（看不懂的再看一遍样例）。
那么这道题怎么做呢？完全想不到KMP啊。。。
但我们好好想想KMP的fail数组，它保存的是当前的串前后有多长相等的，这就和我们要求的很像。
那我们仔细研究一下：
当我们找到最大的一个前后串相等时，那么对于这个原串来说，我们要找小的前后缀相同时，只需要从前面的串找，因为此时我们发现前后缀相同，那么从最后找和从前面和气相同的串找是一样的，所以我们就把原串的问题变成了小串的问题，这样一直向下找，一直找到fail数组为0。但我们这样找的是从大到小，而答案要的是从小到大，所以我们可以用数组存下来，然后倒序输出即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2333333];
int fail[2333333], num[233333];
void init(int m)
{
fail[1] = 0;
for (int i = 2; i <= m; i++)
{
int p = fail[i-1];
while (p && s[i] != s[p+1])
p = fail[p];
if (s[i] == s[p+1])
p++;
fail[i] = p;
}
}
int main()
{
while (scanf("%s", s+1) != EOF)
{
memset(fail, 0, sizeof(fail));
int len = strlen(s+1);
init(len);
int p=fail[len];
int cnt = 0;
while(p)
{
num[++cnt] = p;
p=fail[p];
}
for (int i = cnt; i >= 1; i--)
printf("%d ", num[i]);
printf("%d\n", len);
}
return 0;
}