KMP算法以及 next 数组求解

这几天折腾了下KMP，终于算是理解了其中的原理。现在这里大概记录下，以备不时之需！！

char str[MAXN];    //原串    
char p[MAXN];    //需要在原串中寻找的字符串

相对于一般的字符串匹配，KMP算法优化的地方就在于当发现当前匹配的位置 k + 1 匹配失败时，不是再回到 p 的开始位置进行匹配，而是回到 next[k] 开始匹配！

next[k] 记录了 p[0...k] 中，最长的相同前缀后缀长度 - 1 , -1 是为了转移的时候方便(数组从 0 开始)。

比如：

对于

/*
p:

| a | b | a | a | b | c | a | c |

next:

| -1| -1| 0 | 0 | 1 | -1| 0 | -1|
*/

相同前缀后缀就是前缀和后缀相同；

然后就是 next 数组的求法：

这里照搬一下算法导论中的代码，很巧妙，如果不知道原理模拟一下就清楚了。

void get_next(char *p, int *next){
    next[0] = -1;
    int k = -1;
    for(int i = 1; i < p.length; i++){
        while(k > -1 && p[k + 1] != p[i])
            k = next[k];
        if(p[k + 1] == p[i]){
            k++;
        }
        next[i] = k;
    }
}

有了 next 数组之后，在匹配字符串程序中发现不匹配的位置时，不需要将 p 的位置变量重置为 0 了，将其赋值为 next[k] 就行。

本文只是简单的描述下KMP以备忘，更详细的分析说明可以见网上大神们的博客

using namespace std;
const int maxn = 1000020;
char src[maxn],substring[maxn];
int nxt[maxn];
void get_nxt(char* substring)
{
	int substring_len = strlen(substring);
	memset(nxt, 0, sizeof(nxt));
	nxt[0] = -1;
	int j = -1;
	for(int i = 1; i < substring_len; i++)
	{
		while(j > -1 && substring[i] != substring[j + 1])
			j = nxt[j];
		if(substring[j+1] == substring[i])
			j = j + 1;
		nxt[i] = j;
	}
}

//process src & substring to get the position
int kmp(char* src, char* substring)
{
	int j = -1;
	int ans = 0;
	int substring_len = strlen(substring);
	int src_len = strlen(src);
	for(int i = 0; i < src_len; i++)
	{
		while(j > -1 && src[i] != substring[j + 1])
			j = nxt[j];
		if(src[i] == substring[j + 1])
			j++;
		if(j == substring_len -1)
		{
			ans ++;
	        printf("From position %d to position %d\n", i + 2 - substring_len, i+1);
			j = nxt[j];
		}
	}
	return ans;
}

http://blog.csdn.net/v_july_v/article/details/7041827

秒客网

KMP算法以及 next 数组求解

相关文章