题意：给一个字符串，问该字符串的所有前缀与该字符串的匹配数目总和是多少。
此题要用KMP的next和DP来做。
next[i]的含义是当第i个字符失配时，匹配指针应该回溯到的字符位置。
下标从0开始。
设j=next[i]，那么
如果j==0，回溯到起点说明该字符不匹配。
其他情况，说明字符串S[0,...j-1]与字符串S[0,..i-1]的某个后缀（准确的说是S[i-j,i-1]）相同，这样的话，S[0,..i-1]的后缀（S[i-j,i-1]）一定包含字符串S[0,..i-1]的后缀能够匹配的前缀个数，除此之外，S[0,..i-1]的后缀还应该包括自身这种情况。
设dp[i]表示字符串S[0,..i-1]的后缀可以匹配的前缀个数。
这样dp[i]=dp[next[i]]+1
答案ans=sum{dp[i]}(1<=i<=n)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define MOD 10007
#define MAXN 200005
using namespace std;
char str[MAXN];
int next[MAXN];
int dp[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
scanf("%s",str);
;i<n;++i)
{
int j=next[i];
while(j&&str[i]!=str[j]) j=next[j];
next[i+]=(str[i]==str[j])?j+:;
}
;
;i<=n;++i)
{
dp[i]=(dp[next[i]]+)%MOD;
ans=(ans+dp[i])%MOD;
}
printf("%d\n",ans);
}
;
}