CF 246 div2 D Prefixes and Suffixes (全部前缀的出现次数)

题目链接：http://codeforces.com/contest/432/problem/D

题意：对一个长度不超过10^5的字符串。按长度输出和后缀全然匹配的的前缀的长度，及该前缀在整个串中出现的次数。（可重叠）

#include <cstdio>
#include <cstring>

const int N=100005;

char str[N];
int next[N],cnt[N],ansp[N],ansn[N],n;

void getNext (char s[],int len)
{
    next[0]=-1;
    int i=0,j=-1;
    while (i<len)
    {
        if (j==-1 || s[i]==s[j])
            next[++i]=++j;
        else j=next[j];
    }
}

void KMP ()
{
    int i=0,j=0;
    while (i<n)
        if (j == -1 || str[i] == str[j])
            i++,j++,cnt[j]++;
        else
            j=next[j];

    for (i=n;i>0;i--) //统计每一个前缀出现次数,cnt[i]表示长度为i的前缀出现了cnt[i]次
        if (next[i] != -1)
            cnt[next[i]] += cnt[i];
}

int main ()
{
    scanf("%s",str);
    n=strlen(str);
    memset(cnt,0,sizeof(cnt));
    getNext(str,n);
    KMP();
	int t=n,sum=0;
    while (t) //前缀匹配后缀
    {
        ansp[sum]=t;
        ansn[sum++]=cnt[t];   //
        t=next[t];
    }
    printf("%d
",sum);
    for (int i=sum-1;i>=0;i--)
        printf("%d %d
",ansp[i],ansn[i]);
    return 0;
}