传送门:http://poj.org/problem?id=3461
题目大意:给定一个主串和一个模式,求模式在主串中出现的次数。
解题思路:直接修改标准KMP函数,当匹配成功是不是跳出循环,而是直接按最后一个字符失配的情况去滑动模式串,以获取下一个可能出现的匹配。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1000010,MAXM = 10010;
char T[MAXN],P[MAXM];
int Next[MAXM],N,M,C;
void MakeNext(int M){
int i=0,j=-1;
Next[i] = -1;
while(i<M){
if(j==-1||P[i]==P[j])Next[++i] = ++j;
else j = Next[j];
}
}
int KMP(int pos,int N,int M){
int i = pos, j = 0,ans = 0;
while(i<N){
if(T[i]==P[j]||j==-1)i++,j++;
else j = Next[j];
if(j==M){
ans++;
j = Next[j-1];
i--;
}
}
return ans;
}
int main(){
scanf("%d",&C);
while(C--){
scanf("%s%s",P,T);
N = strlen(T),M = strlen(P);
MakeNext(M);
printf("%d\n",KMP(0,N,M));
}
return 0;
}
分享到:
相关推荐
KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的基本思路是在不回溯主串的...
数据结构书上的KMP算法,书上的算法看的不太明白,自己写了一个,有点罗嗦。 也是自己写的,容易看懂
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
如何用KMP字符串匹配算法求出主串中所包含模式串的总个数 #include using namespace std; void getnext(int next[],string s,int len) { int j=0,k=-1; next[0]=-1; while(j<len){ if(k==-1||s[j]==s[k]){ j...
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...
字符串的模式匹配算法——KMP的C++实现。
讲解完成了KMP模式匹配算法用于查找字符串
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
编程求出子串(模式串)的next值,利用kmp算法实现子串与多个主串的匹配,针对同一子串next值只计算一次。
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
字符串模式匹配KMP实验 字符串模式匹配KMP实验
求模式串在主串的出现位置。给出了求next值及KMP算法。
kmp算法,这是一个解决在输入一个200字符的主串中找到所有所输入的模式串并指出模式串所在的位子的算法。可能有些不足,还望指教 kmp算法,这是一个解决在输入一个200字符的主串中找到所有所输入的模式串并指出模式...
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
串的模式匹配的C语言实现,同时,还会有完好的界面,使用户输入的数据KMP实现与传统实现两种结果进行对比,完全能通过。
代码封装了字符串的kmp模式匹配算法。kmp是一种非常快速的字符串匹配算法,效率比普通匹配算法高很多
《字符串模式匹配KMP算法》教学课例设计[归纳].pdf
在kmp算法中,会出现主串中的一个字符与模式 中的多个相同字符重复地作不必要比较的情形, 这种情况有时使算法的效率降低许多((本文针 对kmp算法的这个缺陷,设计了一种新的算法,减少比较次数,从而提高匹配效率
方法:从主串S中寻找模式串T出现的位置。 基本思想:从主串S的第1个字符起和模式串T的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符再重新和模式的字符比较;依此类推,直到在主串S中...