KMP算法查找串S中含串P的个数count
#include iostream
#include stdlib.h
#include vector
using namespace std;
inline void NEXT(const string T,vectorint next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;iT.size();i◆◆ ){
int j=next[i-1];
while(T[i]!=T[j◆1] j=0 )
j=next[j] ; //递推计算
if(T[i]==T[j◆1])next[i]=j◆1;
else next[i]=0; //
}
inline string::size_typeCOUNT_KMP(const string S,
const string T)
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空,
vectorint next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;indexS.size();◆◆index){
int pos=0;
string::size_type iter=index;
while(posT.size() iterS.size()){
if(S[iter]==T[pos]){
◆◆iter;◆◆pos;
else{
if(pos==0)◆◆iter;
else pos=next[pos-1]◆1;
}//while end
if(pos==T.size()(iter-index)==T.size())◆◆count;
} //for end
return count;
int main(int argc, char *argv[])
string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
coutcountendl;
system("PAUSE");
return 0;
KMP模式匹配算法是一种改进算法,是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的,所以呢人们称它为"克努特－莫里斯－普拉特操作",简称KMP算法.此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作.其改进在于：每当一趟匹配过程出现字符不相等时,主串指针i不用回溯,而是利用已经得到的"部分匹配"结果,将模式串的指针j向右"滑动"尽可能远的一段距离后,继续进行比较.
图1改进算法的模式匹配过程示意
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后再上面的算法中使用.
讲解一下：
当我们分析一个子串时,例如：abcabcddes. 需要分析一下,每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配.然后◆1就行了（别忘了,我们的字符串都是从索引1开始的）当然,不要相同位置自己匹配,默认第一个字符的匹配数是0.
举例如下：
abcabcddes
|----------------------默认是0
--| | |-----------------不能自己相同字符匹配,所以这里者能认为是没有所以是0◆1 =1
-----------| | | |-------不匹配只能取1.
程序写出来就是：
void GetNext(char* T, int *next)
int k=1,j=0;
next[1]=0;
while( k〈 T[0] ){
if (j ==0 || T[k] == T[j])
◆◆k;
◆◆j;
next[k] = j;
else j= next[j];
但是这个不是最优的,因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况,这样前面会出现大量的1,这样的算法复杂度已经和最初的朴素算法没有区别了.所以稍微改动一下：
void GetNextEx(char *T, char *next)
int i=k,j=0; next[1] = 0;
while(k T[0])
if (j == 0 || T[k] == T[j])
◆◆k; ◆◆j;
if (T[k] == T[j])
next[k] = next[j];
else
else j = next[j];
现在我们已经可以得到这个next字符串的值了,此时此刻呢就是KMP算法的本体了：
相当简单：
int KMP(char* S, char* T, int pos)
int k=pos, j=1;
while (k){
if (S[k] == T[j]){ ◆◆k; ◆◆j; }
else j = next[j]
if (jT[0]) return k-T[0];
else return 0;
和朴素算法相比,只是修改一句话而已,但是算法复杂度从O(m*n) 变成了：O(m)
KMP.java
源代码为：
package algorithm.kmp;
/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
*/
public class KMP {
* 对子串加以预处理,从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置,而不是回退到子串的第一个字符,即可提高查找的效率
* 所以呢为了找到这个合适的位置,先对子串预处理,从而得到一个回退位置的数组
* @param B,待查找子串的char数组
* @return
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次,就会找到一个回退位置
for(int i=1;isize;i◆◆){
//当找到第一个匹配的字符时,即j0时才会执行这个循环
//p1
while(j0 B[j]!=B[i]){
j=P[j];
if(B[j]==B[i]){
j◆◆;
//找到一个回退位置j,把其放入P[i]中
P[i]=j;
return P;
* KMP实现
* @param parStr
* @param subStr
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int k =0;
for(int i=0;iparSize;i◆◆){
while(j0 B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
if(B[j]==A[i]){
//输出匹配结果,并且让比较继续下去
if(j==subSize){
k◆◆;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize◆1);
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配,崔卫兵.这个会匹配1次","崔卫兵");
kmp("这个会匹配0次","it1it1it1");
KMP模式匹配算法
include "string. h"
#includeassert. h
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)0)//若 startIndex过大,则无法匹配成功
return (-1);//指向P内部字符的游标
int i;//指向T内部字符的游标
int j=0;//指向P内部字符的游标
for(i= startIndex; i T.strlen(); i◆◆)
{while(P[j]!=T[i] j0)
j=N[j-1];
if(P[j]==T[i])
if(j ==P.strlen())
return(1-j◆1);//匹配成功,返回该T子串的开始位置
return (-1);
基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的,所以呢人们称为KMP算法.此算法可以在O(n◆m)的时间数量级上完成串的模式匹配操作.
其基本思想是：每当匹配过程中出现字符串比较不等时,不需回溯i指针,而是利用已经得到的"部分匹配"结果将模式向右"滑动"尽可能远的一段距离后,继续进行比较.
#include stdio.h
#include string.h
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);
char s[10]="abcacbcba";
int main()
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
int index_KMP(char *s,char *t,int pos)
int i=pos,j=1;
while (i=(int)strlen(s)j=(int)strlen(t))
if (j==0||s[i]==t[j-1])
i◆◆;
else j=next[j];
if (j(int)strlen(t))
return i-strlen(t)◆1;
void get_next(char *t,int *next)
int i=1,j=0;
next[0]=next[1]=0;
while (i(int)strlen(t))
if (j==0||t[i]==t[j])
next[i]=j;
以上就是土嘎嘎小编为大家整理的php实现kmp算法相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！