HDU-3336-Count the string(next数组

Count the string

题意：

• 求所有前缀出现的次数和

思路：

• 由于next数组回退得到的前缀也是主串的后缀，所以所有next回退的次数加上本身的一次取模就是答案。

#include<bits/stdc++.h>
using namespace std;
const int M=200000;
const int mod=10007;
char s[M];
int nxt[M];
void getnext(int len)
{
    int j=0;
    int k=-1;
    nxt[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            k++;
            j++;
            nxt[j]=k;
        }
        else
        {
            k=nxt[k];
        }
    }
}
int main( )
{
    int t,len;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&len);
        getchar( );
        scanf("%s",s);
        getnext(len);
        int ans=len;
        for(int i=len;i>0;i--)
        {
            int k=i;
            while(nxt[k]>0)
            {
                ans=(ans+1)%mod;
                k=nxt[k];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}