首页 > 基础算法 > 字符串处理 > 常用算法-KMP匹配算法(2)优化
2014
02-19

常用算法-KMP匹配算法(2)优化

上一篇:常用算法-KMP算法(1) 讲的是KMP的原始算法,其中next数组的求法并不是常见的写法。

next[0]=0 的初始化在下面的计算中并不方便,大多数算法都是初始化 next[0] = -1; 而且只有next[0]为-1,其他next[i] >= 0.

下面给出更常见的写法:

//常规写法,求next数组的值
void getNext()
{
	int i = 0; //pattern串的下标
	int j = -1; //
	next[0] = -1;
	while (i < pattern_len - 1)
	{
		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;
			next[i] = next[j];
		}
		else
			j = next[j];
	}
}

一样的原理,只是next的数组的含义可能稍有偏差。

但总体来说,Next数组意义:当pattern串失配的时候,NEXT数组对应的元素指导应该用patter串的哪个元素进行下一轮的匹配。

上面的算法是有缺陷的。比如我们的模式串  pattern =“AAAAB”,其中很容易得到next数组为01230。

如果目标匹配串为 “AAAACAAAAB” ,大家可以模拟一下,A要回溯多次。

就是说我们的next数组优化并不彻底。

优化算法:next[i]表示匹配串在i处如果匹配失败下次移到的位置.

 

最终的优化算法代码:

//优化算法,求next数组的值
void getNext2()
{
	int i = 0; //pattern串的下标
	int j = -1; //
	next[0] = -1;
	while (i < pattern_len - 1)
	{

		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;
			if (pattern[i] != pattern[j]) //正常情况
				next[i] = j;
			else //特殊情况,这里即为优化之处。考虑下AAAAB, 防止4个A形成0123在匹配时多次迭代。
				next[i] = next[j];
		}
		else
			j = next[j];
	}
}

虽然两种写求得next值不一样,但是kmp函数的写法是一样的。

参考测试代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int next[100], pattern_len, str_len;
char * pattern, * str;

//优化算法,求next数组的值
void getNext2()
{
	int i = 0; //pattern串的下标
	int j = -1; //
	next[0] = -1;
	while (i < pattern_len - 1)
	{

		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;
			if (pattern[i] != pattern[j]) //正常情况
				next[i] = j;
			else //特殊情况,这里即为优化之处。考虑下AAAAB, 防止4个A形成0123在匹配时多次迭代。
				next[i] = next[j];
		}
		else
			j = next[j];
	}
}

//求next数组的值
void getNext()
{
	int i = 0; //pattern串的下标
	int j = -1; //
	next[0] = -1;
	while (i < pattern_len - 1)
	{
		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int kmp()
{
	int i = 0, j = 0;
	str_len = strlen(str);
	getNext2(); // getNext();
	while (i < str_len && j < pattern_len)
	{
		if (j == -1 || str[i] == pattern[j])
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if (j >= pattern_len)
		return i - pattern_len;
	else
		return -1;
}

void printNext() {
	for (int i = 0; i < pattern_len; i++)
		cout << next[i] << " ";
	cout << endl;

}

void getnext3(){
	int i=0;
	int j= next[0] = -1;
	while( i < pattern_len){
		if( j==-1 || pattern[i] == pattern[j] ){
			i++; j++;
			next[i] = j;
		}else
			j = next[j];
	}
}

int main()
{
	str = "AAAABAAACABAA";
	pattern = "AAACAB";
	pattern_len = strlen(pattern);
	int res = kmp();
	cout << res << endl;
	printNext();

}

 

 


  1. 常见算法是直接按照思路写了就放上来的吧,明显next ==next ,存在问题,而优化的那条,我直接拿过来,带入代码,也是错的

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience