kmp.cpp

kmp 算法 也许会有帮助的。。。大家快来下吧

#include <vector>
#include <time.h>
#include <algorithm>
#include <string>
#include <iterator>
#include <fstream>
#include <iostream>
#include <functional>
#pragma warning(disable:4786) 
#pragma warning(disable:4101)
#define MIN(A,B) ((A) <= (B) ? (A) : (B))
using namespace std;

void get_nextval(const char *T, int next[]) 
{ 
       // 求模式串T的next函数值并存入数组 next。
       int j = 0, k = -1; 
       next[0] = -1; 
       while ( T[j/*+1*/] != '\0' ) 
       { 
              if (k == -1 || T[j] == T[k]) 
              { 
                     ++j; ++k; 
                     if (T[j]!=T[k]) 
                            next[j] = k; 
                     else 
                            next[j] = next[k]; 
              }// if
              else 
                     k = next[k]; 
       }
    for(int i=0;i<j;i++)
       {
            cout<<next[i]<<"  ";
       }
       cout<<endl;
}// get_nextval　

int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{ 
	if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )// 
		return -1 ;//空指针或空串，返回-1。
	int len=0; 
	const char * c=Pattern; 
	while(*c++!='\0')//移动指针比移动下标快。
	{     
		++len;//字符串长度。
	} 
	int *next=new int[len+1];
	get_nextval(Pattern,next);//求Pattern的next函数值
    
	int index=0,i=0,j=0; 
	while(Text[i]!='\0' && Pattern[j]!='\0' ) 
	{ 
		if(Text[i]== Pattern[j]) 
		{ 
			++i;// 继续比较后继字符
			++j; 
		} 
		else 
		{ 
			index += j-next[j]; 
			if(next[j]!=-1) 
				j=next[j];// 模式串向右移动
			else 
			{ 
				j=0; 
				++i; 
			} 
		} 
	}//while
    
	delete []next;
	if(Pattern[j]=='\0') 
		return index;// 匹配成功
	else 
		return -1;       
}
int main()//abCabCad 
{ 
	char* text="bababCabCadcaabcaabaadCadCadbaaacababcaabc"; 
    char*pattern="adCadCad"; 
	//getNext(pattern,n); 
	//int n[10];
   // get_nextval(pattern,n); 
	cout<<KMP(text,pattern)<<endl; 
	return 0; 
}