题目大意
计算所有前缀在字符串中出现的次数
思路
开始想直接枚举所有前缀,用模板计算出现次数加起来就行了,tle了。
看了题解,还是利用next数组,因为要求的是所有前缀出现的次数,那么可以利用dp的思想。
- dp[i]可以理解为字符串长度为i时,相比i-1长度增加的满足条件的次数。
- 那么转移方程就为dp[i] = dp[next[i]] +1。
-
开始一直理解不了dp[next[i]],是什么(很多博客解释是结尾为a[i]时满足条件的次数,明显是不对的),假设字符串为a c a b a c a ,如下图:
- 当长度为1时 { a }:
增加的匹配为S_0一个满足条件 a:
dp[1] = 0 + 1 = 1 - 当长度为2时 { a c }:
相比长度为1,多的还是S_{0-1},一个满足条件的字符串a b:
dp[2] = 0 + 1 = 1 -
当长度为3时 { a c a }:
增加了S_{0-2}这个满足条件的字符串,P[2]与P[0]也可以匹配:
dp[3] = 1 + 1 = 2 - 当长度为4时 { a c a b }:
增加了S_{0-3}满足条件:
dp[4] = 0 + 1 = 1 - 当长度为5时:
除了增加了S_{0-4},S_{0}与S_{4}也能满足条件:
dp[5] = 1 + 1 = 2 - 当长度为6时:
除了多了S_{0-5},S_{0-1}与S_{4-5}也能满足条件:
dp[5] = 1 + 1 = 2 -
当长度为7时:
除了S_{0-6}, S_{0-2}与S_{4-6},S_{0}与S_{6}都能满足
dp[6] = 1 + 2 = 3
最后累加 ans = 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12
- 当长度为1时 { a }:
重点分析长度为7的时候,我们发现我们除了S_{0-6},第一个找到的是S_{0-2}与S_{4-6},也就是字符串的最长公共前后缀,那么我们接下来找的S_{0}与S_{6},其实都包含在最长公共前后缀里,根据kmp的next数组的含义,我们要找的S_{0}与S_{6},应该为k = next[k]长度的该字串的公共前后缀子。
由此我们可以想到转移方程dp[i] = dp[next[i]] +1。从0-n-1就可以得到每次增加的次数了,然后将dp数组累加,就可以得到答案了。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 200002;
int NEXT[MAXN];
int dp[MAXN];
string P;
string T;
int plen;
int tlen;
void getNEXT(){
int k,j;
k = -1;j = 0;NEXT[0] = -1;
while(j<plen){
if(k==-1||P[k] == P[j]){
NEXT[++j] = ++k;
}else{
k=NEXT[k];
}
}
}
int main(){
ios::sync_with_stdio(false);
int TT;
cin>>TT;
while(TT--){
int N;
long long ans=0;
cin>>N>>P;
memset(dp,0,sizeof(dp));
plen = P.length();
getNEXT();
for(int i = 1;i<=N;i++){
dp[i] = dp[NEXT[i]] + 1;
dp[i] %=10007;
}
for(int i = 0;i<=N;i++){
ans += dp[i];
ans %=10007;
}
cout<<ans<<"\n";
}
return 0;
}