http://acm.hdu.edu.cn/showproblem.php?pid=3336
题意:求字串中【前缀+跟前缀相同的子串】的个数?
Sample Input
1
4
abab
Sample Output
6
abab:包括2个a,2个ab,1个aba,1个abab
这里要用到next值的意义:
next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度
举个例子:
next[5]=2, 表示下标5前面那个字符串abcab的前后缀匹配的最大长度是2,显然就是ab了
回到本题:
所求=字串的前缀个数+与前缀相同的子串
问题可以部分转化为:每个前缀的最大前后缀匹配问题
继续用上面的例子:
第一步:
对于这段子串,next[5]=2,然后后面不符合next值的递推规律了
所以对于abcab,长度为2的后缀,即ab与前缀匹配
所以+1个ab,注意还要+1个a,既然后缀ab跟前缀ab匹配,则必有a跟前缀匹配
也就是+2个了,其实实际上+next[5]就可以了,因为这是最长前后缀匹配长度
第二步:
对于这段子串:
next[6]=1,然后后面不符合next值的递推规律了
所以对于abcaba,长度为1的后缀,即a与前缀匹配
所以+1个a,也就是+next[6]了
第三步:
对于整个串:
next[12]=4后面没有了
所以对于整个串:abcabacbabca,长度为4的后缀跟前缀匹配
所以+1个abca,+1个abc,+1个ab,+1个a,总共+4个,也就是+next[12]了
最后:
好了,刚刚一共+了7个与前缀匹配的子串
上面说了题目是求:字串的前缀个数+与前缀相同的子串个数
与前缀相同的子串个数就是7个了
然后字串的前缀个数当然就是整个串的长度了,那么就是12个
加起来就是答案:19
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define L2 200005
int next[L2], len2;
char p[L2];
void get_next () //KMP原始next值
{
int j = 0, k = -1;
next[0] = -1;
while (j < len2)
{
if (k == -1 || p[j] == p[k])
{
j++, k++;
next[j] = k;
}
else k = next[k];
}
}
int main()
{
int t, res, j;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%s", &len2, p);
get_next ();
res = next[len2] + len2; //先包含:最后的next值【第三步】+前缀数【串长】
for (j = 0; j < len2; j++)
if (next[j] > 0 && next[j] + 1 != next[j+1])
res += next[j]; //当不满足递推规律时+next值【第一、二步】
printf ("%d\n", res%10007);
}
return 0;
}
分享到:
相关推荐
KMP算法,详细的解释了如何去匹配字符串。做成了实验报告,希望给大家帮助。
一个封装有KMP模式匹配算法的String类示例,VC++ 2010下编译通过。
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
kmp 字符串匹配 算法 C语言实现 函数
模式匹配,KMP算法,string-match-kmp-master.zip
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
The classical KMP algorithm for string matching (the target string can be modified in the main function, if any match is found, the matching position would be returned)
KMP算法
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
kmp string matching implementation in matlab
数据结构中KMP算法过程的Flash演示
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
BF和KMP算法过程#include #include<string.h> using namespace std; #define N 80 void main() { char S[N],T[N]; int i,j,count=0; cout请输入长串S:"; gets(S); cout请输入子串T:"; gets(T); i=0;j=0; ...
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
用于识别子串 模式匹配算法 KMP算法 输入两个String