关于KMP的next函数的原理分析

KMP是上学期学数据结构时候学的，当时就没学太明白，后来又自己琢磨了几次，但始终是一知半解。今天起床了又想起来KMP，以下是思考得到的一点东西。

首先学过kmp的都知道要写两个函数，一个计算next数组，一个kmp主体函数，那么next数组里存的到底是啥呢。首先答案是：next[i]存的是字符串[0,i]的前后缀最长公共长度减1的值。下面先解释下前后缀。

引用张别人的图：

也就是说只有一个元素时候前后缀都为空，即不能拿整个字符串作为前缀or后缀，注意这点即可。

我们把第i位对应的最大公共前后缀长度减1的值作为next[i]的值，这一点是为了之后计算的方便，后续会提到。

下面是next数组的计算函数

//创建NEXT数组

int create_next(int* address,int len,string str)

{

	address[0]=-1;

	for(int i=1;i<len;i++)

	{

		int k=address[i-1];

		while(str[k+1]!=str[i]&&k>-1)

		{

			k=address[k];

		}

		if(str[k+1]==str[i])

		{

			++k;

		}

		address[i]=k;

	}

}

首先address[0]=-1，原因上面说了。每次for循环里的i是代表字符串的游标，每次for循环干的事是计算出字符串[0,i]的最长公共前后缀元素个数，当然我们可以一个个数，先看str[0]=str[i]成立不成立，再看str[0]=str[i-1]&&str[1]=str[i]成立不成立，依次类推。但是这样重复考察了太多元素，故我们采用简便一点的方法，我画了个图。

如图，前后黑括号代表[0,i-1]的最长公共前后缀，但str[k+1]!=str[i]，那么我们要找黑括号里的更小的蓝括号，让前后蓝括号相同。注意看图，找到满足上面条件蓝括号的时候，左边蓝括号就在左边黑括号的左端，右边蓝括号在右边黑括号的右端，这不就是求[0,k]或者[i-1-k,i-1]的最长公共前后缀长度么?再看下k=next[k]，是不是这回懂为啥这么写了。从最开始的黑括号寻找蓝括号的部分就是next函数第一部分，也就是下面这个while循环做的事情，想一想是不是

 int k=address[i-1];

		while(str[k+1]!=str[i]&&k>-1)

		{

			k=address[k];

		}

找到上面的一对蓝括号之后，就出去while循环了，接下来是：

	if(str[k+1]==str[i])

		{

			++k;

		}

		address[i]=k;

这段意思是：此时k是蓝括号的长度-1，那么k+1就是蓝括号往右第一个元素，如果这个元素等于str[i]，那么公共长度就加1，否则直接返回k。如果从while出来时候k等于-1，那表示找不到这样的蓝括号，那么只能考察str[0]和str[i]了，如果相等公共长度就为1，否则就为0。再看下函数开始，如果address[i-1]就等于-1的话，while循环直接就出来了，出来直接判断str[-1+1]==str[i]成立不成立，所以这里可以看出我们当时为什么要把长度-1作为next数组值。以上，不对的地方请指出，不懂的可以评论交流。

闲着没事又敲了个python的：

def create_next(next_list,str):

    str_len=len(str)

    next_list.clear()

    next_list.append(-1)

    k=-1

    for i in range(str_len):

        while k!=-1 and str[k+1]!=str[i]:

            k=next_list[k]

        if str[k+1]==str[i]:    #若k为-1也成立

            k+=1

        next_list.append(k)

next_list=[]

def KMP(target,pattern):

    #TARGET目标串，pattern模式串

    create_next(next_list,pattern)

    tar_len=len(target)

    pat_len=len(pattern)

    k=-1

    for i in range(tar_len):

        while k!=-1 and target[i]!=pattern[k+1]:

            k=next_list[k]

        if target[i]==pattern[k+1]:

            k+=1

        if k==pat_len-1:    #模式串全部匹配，即匹配成功

            return i-pat_len+1

x="bacbababadababacmbabacaddababacasdsd"

y="ababaca"

print(KMP(x,y))

巴特西

关于KMP的next函数的原理分析

最新文章

热门文章