题目链接：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\n",sum);

    for (int i=sum-1;i>=0;i--)

        printf("%d %d\n",ansp[i],ansn[i]);

    return 0;

}