Codeforces Round #246 (Div. 2) D:http://codeforces.com/contest/432/problem/D
题意：给你一个长度不超过10^5的字符串。要你按长度输出和后缀完全匹配的的前缀的长度。和该前缀在整个串中出现的次数。（可重叠）
题解：老实说，这一题，我完全是看样子看出规律出来的，想到用KMP，就是KMP数组反过来输出就可了，个数就是之前出现的次数加上本身的次数即可。
一下是别人的分析：
若第i个位置和第j个位置匹配了说明前缀j在第i个位置出现了一次。我们用cnt[i]记录。前缀i出现的次数。最后统计cnt[next[i]]+=cnt[i]。这个很好理解。如果前缀j能在i这个位置出现一次那么next[j]一定能在i这个位置出现一次。统计完每个前缀在原串中出现次数后。现在就要找钱缀和后缀匹配的前缀的个数了。这个很简单。自己和自己匹配不就是拿自己的前半部分和自己的其他部分匹配么。所以我们只需要匹配第n+1个位置就可以找出所有和后缀匹配的前缀了。华丽的O(n)就过掉了。。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1e5+8; 7 char p[N]; 8 int f[N]; 9 int counts[100002]; 10 void DFS(int x,int as){ 11 if(x==0){ 12 printf("%d ",as); 13 return; 14 } 15 DFS(f[x],as+1); 16 printf("%d %d ",x,counts[x]+1); 17 18 } 19 int main(){ 20 int n,kase=0; 21 scanf("%s",p); 22 n=strlen(p); 23 f[0]=0;f[1]=0; 24 memset(counts,0,sizeof(counts)); 25 for(int i=1;i<n;i++){//串是从0开始的，但是串的第i位对应f数组的第i+1下标 26 int j=f[i]; 27 while(j&&p[i]!=p[j])j=f[j]; 28 f[i+1]=(p[i]==p[j]?j+1:0); 29 } 30 for(int i=1;i<=n;i++) 31 counts[f[i]]++; 32 for(int i=n;i>=1;i--) counts[f[i]]+=counts[i]; 33 DFS(n,0); 34 }