感谢@nonamenotitle 的指教

题意:

给你个字符串

求所有的前缀=后缀的长度,以及这个前缀(后缀)在整个字符串里面出现了多少次

有一个神奇的东西叫做Z-box

d[i]表示从i开始,和前缀匹配了多少

例如AABAABAABAAB的d分别为

    12 1 0 9 1 0 6 1 0 3 1 0

这题只要求出d就可以了

然后就是利用Z-box的做法,Z-box思路如下

每个d都能组成一段区间(d=0区间为空)

如果当前位置以前在所有区间中,右端点最右的区间

如果这个点在区间内,那么直接利用之前的值,也就是说它在区间内所对应的前面的区间的东西

例如还是刚才那个串

AABAABAABAAB

我们在考虑第11个位置的时候,发现一个匹配到结束的位置(10)是最右的

那么我们我们在的串AAB不管是前面还是后面,都是一样的

所以直接调用f(2)的值(1 2 3与10 11 12相对等价)

但是如果这个匹配超出了预期,就是说匹配到了区间的右端点

就暴力开始往右跑计算

反正随着右端点的推进,一共推进最多n次所以是O(n)的

字符串好神奇啊

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[100005];
int d[100005];
int sum[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%s",a);
    memset(sum,0,sizeof(sum));
    int i;
    int n=strlen(a);
    int maxl=0,maxr=0;
    d[0]=n;
    for (i=1;i<n;i++)
    {
        int t=i-maxl;
        if (i>=maxr)
        {
            d[i]=0;
            for (;;)
            {
                if (a[i+d[i]]!=a[d[i]]) break;
                d[i]++;
            }
            if (i+d[i]>maxr)
            {
                maxl=i;
                maxr=i+d[i];
            }
        }
        else
        {
            d[i]=d[t];
            if (i+d[i]>=maxr) d[i]=maxr-i;
            for (;;)
            {
                if (a[i+d[i]]!=a[d[i]]) break;
                d[i]++;
            }
            if (i+d[i]>maxr)
            {
                maxl=i;
                maxr=i+d[i];
            }
        }
        //printf("%d ",d[i]);
    }
    int ans=0;
    for (i=0;i<n;i++)
    {
        sum[d[i]]++;
        if (d[n-i-1]>i)
        {
            ans++;
        }
    }
    printf("%d\n",ans);
    for (i=n;i>=0;i--)
    {
        sum[i]+=sum[i+1];
    }
    for (i=1;i<=n;i++)
    {
        if (d[n-i]>=i)
        {
            printf("%d %d\n",i,sum[i]);
        }
    }
    return 0;
}