您的当前位置:首 页 >> 信息中心

关于KMP算法的一种个人理解,关于KMP算法中前缀函数(next函数)的一点个人理解

发布日期:2021-10-27 18:09:25 作者: 点击:

最近再刷笔试题的时候,发现了几道题需要求取字符串的next数组。

关于这部分知识,之前是有学过,代码也是比较简洁的,如下:

public static int[] getNext(String ps) {char[] p = ps.toCharArray();int[] next = new int[p.length];next[0] = -1;int j = 0;int k = -1;while (j < p.length - 1) {if (k == -1 || p[j] == p[k]) {next[++j] = ++k;} else {k = next[k];}}return next;} 但是对于KMP的描述,《算法导论》等教材中是有些隐晦复杂的,各个博客上的讲解也不尽相同。针对next数组这一块,综合了几家之长,我也简单描述下自己的想法,可以与大家相互探讨。

因为在kmp算法中,文本中的指针i是无法回溯的,所以最关键的是,next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置。其中P为匹配字符串,T为原文。也就是说next数组其实就是查找P中每一位前面的子串的前后缀有多少位匹配,从而决定j失配时应该回退到哪个位置。

作为笔试题来说,思想比较简单。就是考虑从P[0 ~ k-1] == p[j-k ~ j-1]中k的个数,基本就可以数出来了。借用他人的说法就是(字符串匹配是 从头开始的 和 从尾开始的字符串进行匹配是否重复 )

而在计算next数组时主要是以下两个步骤:

1. 当P[k] == P[j]时,有next[j+1] == next[j] + 1。

2. 当P[k] != P[j]时,有k = next[k]。

结合1和2可知,next[j]==k;

也就是说,P[0 ~ k-1] == p[j-k ~ j-1]中k的位置决定了next[j]的值。

以下列字符串为例:

跑了一下,结果如下:

相信对每一行逐行分析后,会对求取前缀函数有更深的了解