博客

（1）KMP算法

KMP算法是一种字符串匹配算法。学习这种字符串匹配算法最好是以例子的形式理解其思想。推荐一个用图片说明算法过程的博客，浅显易懂：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

（2）算法实现

#include <iostream>

using namespace std;

int kmp(char* str, char* pattern)
{
	if(str == NULL || pattern == NULL)
		return -1;
	int p_len = strlen(pattern);
	int* next = new int[p_len];
	next[0] = -1;
	for(int i=1; i<p_len; ++i)
	{
		int pre = next[i-1];
		while(pre>=0&&pattern[pre+1]!=pattern[i])
			pre = next[pre];
		if(pattern[pre+1] == pattern[i])
			next[i] = pre+1;
		else
			next[i] = -1;
	}
	for(int i=0; i<p_len; ++i)
		cout<<next[i]<<' ';
	cout<<endl;
	int i =0 , j=0;
	int str_len = strlen(str);
	while(j<str_len)
	{
		while(i<p_len&&j<str_len&&pattern[i] == str[j])
			++i,++j;
		if(i==0)
			++j;
		else if (i==p_len) 
			return j-p_len;
		
		else
           i = next[i-1]+1;
	}
	return -1;
}

int main()
{
   char* s = "ababfababc";
   char* p = "ababc";
   cout<<kmp(s, p)<<endl;
   return 0;
}