KMP算法实现才 c++

kmp算法可以有效提高字符串匹配的速度，当匹配字符串中出现较多循环节时尤其有效，但是当一个字符串中几乎每一个字符都不相同的时候，kmp算法并不能很好的加速整个匹配过程，但是光思想就可以甩brute-force算法几条街。下面给出了两种算法的具体实现，对于kmp算法，其关键思想是：当与源字符串出现不匹配时，无需从头再来，而是可以只退回到next[j]的位置，j为当前匹配字符串的位置，所以kmp算法的关键在与如何求解next数据，下面是计算next数组的公式，根据公式实现方法很多，但是万变不离其宗：

{ 0-1 when j=0

next[j]= { max{k|0<k<j|"t0...tk-1"=="tj-k.....tk-1"}

{ 0 else

下面是两种算法的实现代码，main函数仅供测试：

（1）、brute-force算法

#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
   *Author:hujian
   *Time:2016/5/22
   *description:the pre-KMP algorithm
   *it can solve some sample problem,but not so easy to
   *handle the big-data.
   *
*/


using namespace std;


int brute_force(string src,string dst)
{
  int i=0,j,k;
  while(i<src.length()){
 	for(j=i,k=0;j<src.length()&&k<dst.length()&&src[j]==dst[k];j++,k++);
	if(k==dst.length()){
	  //i find the position
	  return i;
	}
      i++;
   }
  return -1;//return -1 means i can not find the sub-str in src string
}


int main(int argc,char**argv)
{
   if(argc!=3){
	printf("usage:%s [src-string] [dst-string]\n",argv[0]);
       return !0;
   }
   else if(brute_force(argv[1],argv[2])!=-1){
	printf("[%s] include  [%s]\n",argv[1],argv[2]);
   }
   else{
       printf("[%s] do not include [%s]\n",argv[1],argv[2]);
   }
  return 0;
}

（2）、kmp算法

#ifndef _KMP_TEMPLATE_H_
#define _KMP_TEMPLATE_H_

#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;
int Next[100001];
string s,p;

//get next array
void getnext(int len)
{
  int j,k;
  j=0,k=-1,Next[0]=-1;
  while(j<len){
      if(k==-1||p[j]==p[k]){
        j++,k++;
        Next[j]=k;
      }else{
        k=Next[k];
    }
  }
}
//
//kmp
//@ls:ls is length of source string
//@lp:lp is length of pattern string
//
int kmp(int ls,int lp)
{
	int i = 0, j = 0;
	getnext(lp);	
	while (i < ls&&j < lp){
           if (j == -1 || s[i] == p[j]){
	       i++, j++;
	    }else{
		j = Next[j];
	    }
	    if (j == lp){//kmp ok.
		return (i-lp);	
	    }
	}
  return -1;//-1 means i can not pattern the str in src string
}
int main(int argc,char**argv)
{
   if(argc!=3){
     printf("usage:%s [src] [pattern]\n",argv[0]);
     return -1;
   }
   s=argv[1],p=argv[2];
   cout<<"s="<<s<<"  p="<<p<<endl;
   int res=kmp(s.length(),p.length());
   if(res!=-1){
      printf("[%s] contain [%s] at>>>>>>>>>>>>>>>[%d]\n",argv[1],argv[2],res);
   }
   else{
      printf("[%s] not contain [%s]\n",argv[1],argv[2]);
   }
   return 0;
}

#endif  //end of kmp template header
///<2016/5/23> hujian nankai university
///<theme:kmp>

秒客网

KMP算法实现才 c++

相关文章