广告

蒟蒻のblog

更新现场（建议先看“思路”开始的部分）

鉴于评论区的大家对代码中的ans提出的疑惑，我再重新细讲一遍

考虑kmp过程中求出的next数组，也就是我的代码里面的fail

实际上这些fail作为边的话，它们构成了一个树形结构。这个树形结构就是KMP自动机的fail树（关于fail树的概念可以参考AC自动机，这里实际上KMP自动机就是在AC自动机只插入了一个字符串的情况下建立的自动机，同理它也拥有fail树）（同时也要注明，实际上此处使用的应该是MP算法而不是KMP算法，所以称之为MP自动机更合适）

那么理解了这个以后，就可以轻松意识到，代码里面的ans实际上是这个节点在fail树上的深度

应当意识到，由于对于前缀i而言，next[i]、next[next[i]]、next[next[next[i]]]等等都是它的公共前后缀，所以节点i在该字符串的KMP自动机的fail树上的深度就是前缀[1,i]的公共前后缀个数

在后面的递归求解过程中，如果把这个过程放到fail树上理解，同样会好理解很多：j也就是在fail树上往前跳的过程中用于记录的一个指针，它会每次跳到直到j\ast 2>i为止

思路

首先，这题最好的一个地方，在于它给出的关于next的讲解实在是妙极......甚至可以说我的kmp是过了这道题以后才脱胎换骨的

然后是正文：

如何求num数组？

这道题的输入有1e6个字符，显然需要O\left(n\right)左右级别的算法来解

先看到num的定义：不互相重叠的公共前后缀个数

这说明什么？

说明num不同于next记录的是一个最大值，它记录的是一个和值

而这个和值，是可以推出来的

考虑一个前缀i的next[i]，它长这样：

其中，next[i]，next[next[i]]，next[next[next[i]]]......都是这个前缀串i的公共前后缀，而且只有它们是公共前后缀

那么，我们其实只要在求next的过程中，顺便把这个公共前后缀的数量递推一下，就得到了一个弱化版的num数组：可以重叠的公共前后缀数量，我们称之为ans

如何去除有重叠的？

还是看上面那张图

首先next数组有一个性质：next[i] < i

也就是说，一旦有一个递归了n层的next，比原前缀i的长度的一半要小，那么这个next的递推出的答案ans就是i的num了

一个问题

假如我们拿到的串是1e6个'a'，那么上面那个算法就会被卡成O\left(n^2\right)，道理的话大家可以想一想（每一次递归都只会把next[i]变小1）

那么我们需要做一个优化，来解决这个问题，而解决问题的核心就是：减少重复递归

减少重复递归......有没有想到什么？

没错，就是如同求next时一样的方法！

我们将递归用的变量j的值不更新，这样，求完了i的答案以后，j的位置一定在\frac i2的左边，也就是它已经满足要求了

这时再递归求解，总时间效率是O\left(n\right)的

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
int n,fail[1000010],ans[1000010];ll cnt;char a[1000010];
int main(){
    int T,i,j;scanf("%d",&T);
    while(T--){
        scanf("%s",a);n=strlen(a);
        memset(fail,0,sizeof(fail));
        j=0;ans[0]=0;ans[1]=1;

        for(i=1;i<n;i++){//求解next
            while(j&&(a[i]!=a[j])) j=fail[j];
            j+=(a[i]==a[j]);fail[i+1]=j;ans[i+1]=ans[j]+1;//递推记录ans
        }

        j=0;cnt=1;
        for(i=1;i<n;i++){//求解num
            while(j&&(a[i]!=a[j])) j=fail[j];
            j+=(a[i]==a[j]);
            while((j<<1)>(i+1)) j=fail[j];
            cnt=(cnt*(ll)(ans[j]+1))%MOD;//记得+1
        }
        printf("%lld\n",cnt);
    }
}