hdu_3336: Count the string(KMP dp)

题目链接

题意:求给定字符串中,可以与某一前缀相同的所有子串的数量

做这道题需要明白KMP算法里next[]数组的意义

首先用一数组nex[](这里与之前博客中提到的next明显不同)存储前缀后缀最长公共元素长度。(nex[i]表示,在S[1~i](在标号从1开始的情况下)这个字串中,前缀后缀最长公共元素长度

然后使用一数组dp[],dp[x]中存放 S[1~x]*含有 以S[x]结尾的&&与某一字串相同 字串的个数

这样递推一下,然后把所有dp[i]求个和就是ans了

#include<bits/stdc++.h>
using namespace std; const int N=2e5+;
const int mod=;
char T[N],S[N];
int nex[N];
int dp[N];
int slen; void getNext()
{
int j,k;
j=;k=-;nex[]=-;
while(j<slen)
if(k==-||S[j]==S[k])
nex[++j]=++k;
else
k=nex[k];
}
void printNext()
{
for(int i=;i<slen;i++)
printf("%3c",S[i]);
puts("");
for(int i=;i<=slen;i++)
printf("%3d",nex[i]);
puts("");
for(int i=;i<=slen;i++)
printf("%3d",dp[i]);
puts("");
} int main()
{
int t;scanf("%d",&t);
while(t--)
{
scanf("%d",&slen);
scanf("%s",S);
getNext();
int sum=;
for(int i=;i<=slen;i++)
{
dp[i]=dp[nex[i]]+;
sum=(sum+dp[i])%mod;
}
// printNext();
printf("%d\n",sum);
}
}
/*
55
6
111111
6
121212
6
123123
*/
上一篇:NYOJ 1067 Compress String(区间dp)


下一篇:[安卓] 19、一个蓝牙4.0安卓DEMO