Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 14761 | Accepted: 7407 |
Description
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
Source
#include <cstdio>
using namespace std; const int N(4e5+);
char s[N];
int nt[N], ans[N]; int main(){
for(int ls, cnt; ~scanf("%s", s);){
for(int i=ls=, k=; s[i]; i++, ls++){
while(k&&s[k]!=s[i]) k=nt[k-];
nt[i]=s[k]==s[i]?++k:k;
}
for(int i=(cnt=,ls); i; ans[cnt++]=i, i=nt[i-]);
for(; cnt; printf("%d ", ans[--cnt])); puts("");
}
}
代码有亮点
for(int i=(cnt=,ls); i; ans[cnt++]=i, i=nt[i-]);