题目描述

给定长度为 $L$ 的字符串，定义 $num_i$ 为对于该字符串长度为 $i$ 的前缀子串，满足该前缀的长度为 $(t\leq \lfloor \frac{i}{2}\rfloor)$ 的后缀与长度为 $t$ 的前缀相等的后缀数。求
$$ ∏^L_{i=1}(num[i]+1) $$

解法

现有其他题解均使用 KMP 解决本题。本篇题解提供 $Z$ 函数解法。

$Z$ 函数的定义、求法等此处不进行介绍，提供一道比较好的模板题：AcWing160 匹配统计

容易考虑的一点是，位置 $i$ 可以对 $\forall j \in[i,min\{ i+Z_i-1,2i\}]$ 的 $num_j$ 作出 $1$ 贡献。

因此我们可以在求 $Z$ 函数值的过程中维护一个区间加法。

区间加可以用树状数组维护，但考虑到本题不涉及动态查询，用树状数组维护会让复杂度多一个 $log$，使用差分维护即可。最后做一次前缀和即可得到所有位置 $num$ 的值。

用 KMP 求解本题需要一定的思考，但是如果用 $Z$ 函数本题就完全是模板题了。难度不高。

代码

#include<cstdio>
#define mian main
const int MOD=1e9+7;
int z[1000086],num[1000086],f[1000086],ans,n,len;
char st[1000086];
int Min(int a,int b){return a<b?a:b;}
int mian(){
    scanf("%d",&n);
    while(n--){
        len=0;
        char ch=getchar();
        while(ch<'a'||ch>'z')ch=getchar();
        while(ch>='a'&&ch<='z')st[++len]=ch,ch=getchar();
        for(int i=1;i<=len;i++)z[i]=num[i]=0;
        for(int l=0,r=0,i=2;i<=len;i++){
            if(i<=r)z[i]=Min(r-i+1,z[i-l+1]);
            while(z[i]<len&&st[z[i]+1]==st[i+z[i]])z[i]++;
            if(i+z[i]-1>r)l=i,r=i+z[i]-1;
            num[i]++;num[Min(2*i-1,i+z[i])]--;
        }
        long long ans=1;
        for(int i=2;i<=len;i++){
            f[i]=f[i-1]+num[i];
            ans=ans*(f[i]+1)%MOD;
        }
        printf("%lld\n",ans);
    }
}