t<=5次询问每次问一个<=1e6的串的$\sum_{i=1}^{n} (num_i+1)$，其中num[i]表示既是前缀i的前缀又是前缀i的后缀且这两部分不重叠的子串的数量。

方法一：在KMP树上倍增！吃枣药丸+tle+制杖

方法二：开另一个数组记下每个点在KMP树中的深度，另外开一个指针记下“前后不重叠”的匹配不就完了。。

1 #include
      
        2 #include
       
         3 #include
        
          4 //#include
         
           5 #include
          
            6 //#include
           
             7 using namespace std; 8 9 int t,n;10 #define maxn 100001111 char s[maxn];int fail[maxn],cnt[maxn];12 const int mod=1e9+7;13 int main()14 {15 scanf("%d",&t);16 while (t--)17 {18 scanf("%s",s+1); n=strlen(s+1);19 int f1=0,f2=0; fail[1]=0; cnt[0]=-1; cnt[1]=0;20 int ans=1;21 for (int i=2;i<=n;i++)22 {23 while (f1 && s[i]!=s[f1+1]) f1=fail[f1];24 if (s[i]==s[f1+1]) f1++;25 fail[i]=f1; cnt[i]=cnt[f1]+1;26 27 while (f2 && s[i]!=s[f2+1]) f2=fail[f2];28 if (s[i]==s[f2+1]) f2++;29 while (f2 && f2*2>i) f2=fail[f2];30 ans=1ll*ans*(cnt[f2]+2)%mod;31 }32 printf("%d\n",ans);33 }34 return 0;35 }