hduCount the string——对kmp的next数组的理解和运用

题目链接

思路：

next数组，ne[i] = j,表示s[1, j] 和 s[i-j+1,i] 相等，即从i结尾长度为j的后缀和从1开始长度为j的前缀相等 (s字符串从1开始存储）
ans初始化为n，如果发现ne[i]>0,则ans++,再进行回溯，直到ne[i]==0

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5+9;
char s[N];
int  ne[N];
typedef long long ll;
const int mod = 10007;
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int n;
        scanf("%d %s",&n,s+1);
        int ans = n;
        memset(ne,0,sizeof ne);
    for (int i = 2, j = 0; i <= n; i ++ )
{
   
    while (j && s[i] != s[j + 1]) j = ne[j];
    if (s[i] == s[j + 1]) j ++ ;
    ne[i] = j;
   // cout<<ne[i]<<endl;
}
        for(int i=2; i<=n;i++)
        {
   
            int t = ne[i];
            while(t)
            {
   
                ans = (ans+1 )%mod;
                t = ne[t];
            }
       }
       printf("%d\n",ans); 
}
return 0;
 }