首先得到主串的next数组，next数组的含义是next[j]的值表示str[0...j-1]（我的next[0]是-1）这个子串的前后缀匹配的最长长度，如样例1

index  0  1  2  3  4  5  6  7

str    A  B  A  C  A  B  A

next   -1 0  0  1  0  1  2  3

next[6] = 2即ABACAB这个子串的前后缀最长匹配是2(AB)，此时表明存在前缀与后缀匹配长度为2的串。

由此性质我们可以发现满足条件的子串即是next[next[len。。。]]不断往前递归直到为0，因为长的可能会包含短的，我们可以递归得到re数组(re记录的就是子串出现的次数)re数组的递归式为re[next[i]] += re[i];

#include <cstdio>

#include <cstring>

int const MAX = 1e5 + ;

char s[MAX];

int next[MAX];

int len, pos, num;

int l[MAX], cnt[MAX], re[MAX];

void get_next(){

    int i = , j = -;

    next[] = -;

    while(s[i] != '\0') {

        if(j == - || s[i] == s[j]){

            i ++;

            j ++;

            next[i] = j;

        }else

            j = next[j];

    }

}

void solve(){

    for(int i = ; i <= len; i++)

        re[i] = ;

    for(int i = len; i >= ; i --)

        if(next[i] != -)

            re[next[i]] += re[i];

    int pos = len;

    while(pos){

        cnt[num] = re[pos];//次数

        l[num ++] = pos;//长度

        pos = next[pos];

    }

}

int main(){

    scanf("%s", s);

    len = strlen(s);

    get_next();

    solve();

    printf("%d\n", num);

    for(int i = num - ; i >= ; i--)

        printf("%d %d\n", l[i], cnt[i]);

}