首先明确 $num_i$ 表示的是不相交的相等前后缀的个数，而非最长长度，被这个卡了很久……

题面大费周章向你介绍了前缀函数（即 $next$ 数组），肯定不是给你白介绍的，我们考虑怎样通过前缀函数推出 $num$ 数组。

这里设前缀 $s[1\cdots i]$ 的前缀函数是 $\pi_i$，分类讨论：

• $2\pi_i\leq i$：皆大欢喜，最长相等的前后缀都没有相交，所有的前后缀都是满足条件的。
• $2\pi_i>i$：最长的前后缀相交了，考虑找到次长的相等前后缀，也就是说我们要找到一段更短的后缀和更短的前缀相等。由于这段前缀一定被最长相等前后缀包含，所以最长后缀也一定拥有一段相等的前缀，那么我们只要找到一段最长后缀的后缀和最长后缀的前缀相等即可，根据前缀函数定义这就是 $\pi_{\pi_i}$。

对于每个点我们只要找到第一个不相交的前后缀，然后统计数量即可，朴素的想法是暴力跳前缀函数，但这无法通过。

考虑倍增，类似 $Sparse-Table$ 那样求出从 $i$ 跳 $2^k$ 次后的前缀函数，这样我们可以直接跳到第一个满足要求的位置，再跳到 $0$ 统计数量即可，时间复杂度 $O(TL\log L)$。

虽然有更优秀的 $O(TL)$ 做法，这种倍增算法略作卡常之后已经足够通过此题。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1000000007;
int t,n,pi[21][1000001],ans;
char s[1000001];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;++i)
            for(int j=0;j<=20;++j)
                pi[j][i]=0;
        for(int i=2;i<=n;++i)
        {
            int j=pi[0][i-1];
            while(j>0&&s[i]!=s[j+1])
                j=pi[0][j];
            if(s[i]==s[j+1])
                ++j;
            pi[0][i]=j;
            for(int j=1;j<=20;++j)
            {
                pi[j][i]=pi[j-1][pi[j-1][i]];
                if(!pi[j][i])
                    break;
            }
        }
        ans=1;
        for(int i=1;i<=n;++i)
        {
            int pos=i;
            for(int j=20;~j;--j)
                if((pi[j][pos]<<1)>i)
                    pos=pi[j][pos];
            pos=pi[0][pos];
            if(!pos)
                continue;
            int sum=0;
            for(int j=20;~j;--j)
                if(pi[j][pos])
                {
                    pos=pi[j][pos];
                    sum|=1<<j;
                }
            ans=1ll*ans*(sum+2)%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

2023.1.8 没想到这居然还能更新。

一种新鲜的线性做法。考虑加速跳 fail 树的过程，如果前缀函数小于一半我们就正常跳，否则根据 border 那套理论我们可以直接把周期快速跳过，即跳到 $|S|\% d+d$，然后如果这个地方已经小于一半了我们就倒着回去找第一个小于等于一半的位置，因为前面一段一直在等距离的跳所以是能直接 $O(1)$ 算出来的。如果这个位置还大于一半就继续迭代，显然这里迭代的次数是常数次，因为每次近似于长度缩小了一半。

时间复杂度 $O(TL)$。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int mod=1e9+7;
int t,n,pi[1000001],ans,dep[1000001];
string s;
inline void init()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
}
inline int read()
{
    int x;
    cin>>x;
    return x;
}
int main()
{
    init();
    t=read();
    while(t--)
    {
        cin>>s;
        n=s.length();
        s=" "+s;
        ans=1;
        dep[1]=1;
        for(int i=2;i<=n;++i)
        {
            int j=pi[i-1];
            while(j&&s[i]!=s[j+1])
                j=pi[j];
            if(s[i]==s[j+1])
                ++j;
            dep[i]=dep[pi[i]=j]+1;
            int d=0,pos=i;
            while(1)
            {
                if(pi[pos]<=(pos>>1))
                {
                    pos=pi[pos];
                    if(pos<=(i>>1))
                        break;
                }
                d=pos-pi[pos];
                pos=pos%d+d;
                if(pos<=(i>>1))
                {
                    pos+=((i>>1)-pos)/d*d;
                    break;
                }
            }
            ans=1ll*ans*(dep[pos]+1)%mod;
        }
        cout<<ans<<'\n';
    }
    cout.flush();
    return 0;
}