题意:
给定一个串,求用该串所有前缀去匹配这个串次数的总和.
分析:
失配指针数组的应用: dp[i] 表示 S[0,i-1] 串的后缀能匹配的前缀的个数.则dp[i] = dp[f[i]] + 1; 初始化 dp[1]=1;
这里用到的就是失配指针的含义：后缀与前缀.
#include<bits/stdc++.h>using namespace std;
const int maxn = 1e7;
char p[maxn],f[maxn],dp[maxn];
const int mod = 10007;
int n,m;
void getfail()
{f[0]=f[1]=0;for(int i=1;i<m;i++){int j=f[i];while(j && p[i]!=p[j])j=f[j];f[i+1]= p[i]==p[j]?j+1:0;}
}int main()
{int k;cin>>k;while(k--){scanf("%d %s",&m,p);getfail();dp[0]=0;int ans=0;for(int i=1;i<=m;i++){dp[i]=dp[ f[i] ]+1;dp[i]%=mod;ans=(ans+dp[i])%mod;}cout<<ans<<endl;}
}