题意

计算所有S的前缀在S中出现了几次

思路

跟前缀有关的题目可以多多考虑KMP的NEXT数组

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cstdlib>

using namespace std;

char S[2000000];

int NEXT[2000000];

int dp[2000000];//dp[i] 表示 以i结尾的子串与前缀相等的个数 d[i]=d[next[i]]+1;

                //一开始还以为是 d[i]=next[i]+1; 在abab这个样例中 d[3]=3 显然有重复计算了

int len;

int sum=0;

void get_next()

{

    for(int i=1;i<=len;i++)

    {

        int p=i-1;

        while(S[i]!=S[NEXT[p]+1]&&p!=0) p=NEXT[p];

        if(p!=0) NEXT[i]=NEXT[p]+1;                 //这种不else 的写法注意清空NEXT

        //else NEXT[i]=0;

    }

}

int main()

{

//  freopen("a.in","r",stdin);

    int T;

    cin>>T;

    while(T--)

    {

        sum=0;

        cin>>len;

        memset(NEXT,0,sizeof(NEXT));

        scanf("%s",S+1);

        get_next();

        for(int i=1;i<=len;i++)

        {

            dp[i]=dp[NEXT[i]]+1;

            sum=(sum+dp[i])%10007;

        }

        cout<<sum<<endl;

    }

}