理解了好久才勉强理解。。。
题目求的是给定字符串s的所有前缀在字符串里出现的次数总和(特么匹配次数不能算重复的。。。然后样例也不说清楚。。。全世界好像就我在这里被卡住。。。)
定义一个dp数组,dp[i]
表示前i个字符里前缀出现的总次数,所以题目求的就是dp[n]
然后递推关系就是dp[i]=dp[i-1]+1+(nex[i]==0?0:1)
这个递推关系前部分很好理解,就是前i-1个字符的状态再加1,就是加上i这个字符形成的一个新的前缀,这暂时肯定只出现1次,所以加1
后部分根据nex数组来判断,因为nex数组表示的就是前i个字符的最大前缀后缀相同的长度,所以如果nex[i]不等于0,说明这前i个字符加上这个第i个字符就有了一个后缀等于前面的前缀,那么也就是说前面的那个前缀又多出现了一次,那就得加1,否则加0,为什么只加1个呢,难道不会出现aaa…aaa这种情况,很多个前缀都出现多了一次,这是因为前面的情况已经在前面的递推中累加了,所以只考虑第i位即可
#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int MOD=10007;
int nex[N],dp[N];
int t,n;
char s[N];
void getNext(char p[]){
int n=strlen(p);
int i=0;
int j=-1;
nex[0]=-1;
while(i<n){
if(j==-1 || p[i]==p[j]){
nex[++i]=++j;
}else{
j=nex[j];
}
}
}
int main(void){
scanf("%d",&t);
while(t--){
int cnt=0;
memset(dp,0,sizeof(dp));
scanf("%d",&n);
scanf("%s",s+1);
getNext(s+1);
//坑点:字符串匹配个数不能算重叠
//dp[i]表示前i个字符里前缀出现的总次数
for(int i=1;i<=n;i++){
dp[i]=(dp[i-1]+1)%MOD;
if(nex[i]){
dp[i]++;
}
}
printf("%d\n",dp[n]%MOD);
}
return 0;
}