kmp.cpp

kmp算法：查找一个字符串是不是另一个字符串的子串

#include <vector>
#include <string>
using namespace std;
const vector<int> * kmp_next(string &m) // count the longest prefex string ; 
{ 
	static vector<int> next(m.size()); 
	next[0]=0; // the initialization of the next[0]; 

	int temp; // the key iterator...... 
	size_t nSz = next.size(), i;
	for(i = 1; i < nSz; i++) 	
	{ 
		temp=next[i-1]; 
		while(m[i] != m[temp] && temp>0) 
		{ 
			temp=next[temp-1]; 
		} 

		if(m[i] == m[temp]) 
			next[i] = temp + 1; 
		else next[i] = 0; 
	} 
	return &next; 
} 
bool kmp_search(string text,string m,int &pos) 
{ 
	const vector<int> * next = kmp_next(m); 

	int tp = 0; 
	int mp = 0; // text pointer and match string pointer; 
	int nSz = (int)text.size();
	for(tp = 0;tp < nSz; tp++) 
	{ 
		while(text[tp] != m[mp] && mp) 
			mp = (*next)[mp-1]; 

		if(text[tp] == m[mp]) 
			mp++; 

		if(mp == m.size()) 
		{ 
			pos = tp - mp + 1; 
			return true; 
		} 
	} 

	if(tp == text.size()) 
		return false; 
}