笔者学习串的匹配时,就是在目标串(主串)中找到与模式串(子串)一样的部分,返回它的子串位置的操作,这叫串的模式匹配。
一种效率低的算法,主串与子串从第一个字符进行比较,直到某一个不相等,然后主串退回到第二个字符重新开始,子串重新从首字符开始与主串进行匹配,一直循环进行比较,这样的话,就存在主串与子串前几个字符已经相等了,可是重新匹配时,又要重新进行比较,每次匹配没有利用前一次匹配的结果,使得算法中存在较多的重复比较,降低了算法效率。
KMP 算法,很好的利用了上次匹配的结果,目标串不会回溯,效率大大增强,在网上也看了很多博客,有了一个比较深的认识,现在尽量写的通俗易懂,希望可以帮助到各位。
假设目标串 target="t0 ...tn", 模式串 pattern="p0...pm", 依次进行比较,如果遇到不相等的字符,目标串的下标 i 不回溯,而模式串有一个下标 k 来决定模式串跳到对应下标为 k 的字符,也就是目标串"ti...tn"与"pk...pm" 进行依次匹配,所以计算 k 值变得非常重要,这个也是 KMP 算法的核心。
模式串的每一个 pj 对应的 k 值都不同,所以定义了一个 next 数组来存储。这里就有一个前缀后缀的概念,前缀子串就是从第一个字符开始,除了最后一个字符,所组成的各种子串形式,后缀相反。比如字符串 "abcad" 的前缀子串为 a,ab,abc,abca, 后缀子串分别为 d,ad,cad,bcad。
next[j] 的值就是 k, 也就是最大前缀后缀子串的长度。假定 next[0]=-1。举个例子,模式串 "abcabc" 的 j 对应的 k 值,见下表:
j | 0 | 1 | 2 | 3 | 4 | 5 |
模式串 | a | b | c | a | b | c |
最长相同前后缀子串的长度 k | -1 | 0 | 0 | 0 | 1 | 2 |
接下来就是如何计算 next 数组,
KMP 算法充分利用前一次计算的结果,由 next[j] 逐个递推计算得到 next[j+1];
约定 next[0]=-1, 而且 next[1]=0; 对于 next[j]=k 知,"p0...pj-1"中有最长为 k 的前缀子串和后缀子串相等,也就是"p0...pk-1"="pj-k...pj-1", 接下来就是 next[j+1], 则 "p0...pj"中求最长前缀后缀子串,因为 next[j]=k, 所以只需求 pk 是否等于 pj, 如果等于,则 next[j+1]=next[j]+1=k+1, 如果不相等,在 "p0...pj"中找较短的前缀后缀子串,只需求 next[k] 即可得到新的 k 值,即 next[j+1]=k+1。
还有一种改进了的计算 next 数组的方法,比上述方法的效率更高,就是在匹配 pj 不等于 ti 之后,比较一下 Pj 和 pk(此时,k=next[j]) 的大小,如果不相等,就 next[j]=k, 如果恰好相等,就不用再比较 ti 和 pk 的值了,肯定不相等,下次匹配从 pnext[k] 开始比较,next[j]=next[k],比较的次数就减小了。
至此,KMP 算法就说完了,代码附上加以理解。
- public class KMP {
- private static int[] next;
- public static int indexOf(String target, String pattern) {
- return indexOf(target, pattern, 0);
- }
- public static int indexOf(String target, String pattern, int begin) {
- // 返回目标串从begin开始,模式串与目标传匹配的序号
- int n = target.length(),
- m = pattern.length();
- int i = begin,
- j = 0;
- next = getNext(pattern);
- // next=getNexts(pattern);
- if (i < 0) i = 0; // 对开始的位置begin进行容错处理
- if (i >= n || n == 0 || m > n) return - 1; // 目标串为空或比模式串短或开始位置越界,不进行比较
- while (i < n && j < m) {
- if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
- i++;
- j++;
- } else { // 若匹配不成功,目标串下标i不回溯
- j = next[j]; // 获得模式串下一趟开始匹配的下标
- if (n - i + 1 < m - j + 1) break; // 目标串的长度不够模式串的长度,不进行比较
- }
- }
- if (j == m) {
- return i - j; // 返回匹配的子串序号
- }
- return - 1;
- }
- // next数组的计算
- public static int[] getNext(String pattern) {
- int j = 0,
- k = -1,
- next[] = new int[pattern.length()];
- next[0] = -1;
- while (j < pattern.length() - 1) {
- if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
- j++;
- k++;
- next[j] = k; // 在"p0~pj-1"串中存在为k的相同前缀和后缀子串
- // next[j+1]求在"p0~pj"中找相同前缀和后缀子串,只需判断pk和pj的值是否相等
- // 相等,就next[j+1]=next[j]+1=k+1
- } else {
- k = next[k]; // 不相等,则找较短的相同前缀和后缀子串,长度k为next[k],再比较,相等则next[j+1]=next[k]+1
- }
- }
- return next;
- }
- // 改进后的next数组计算
- public static int[] getNexts(String pattern) {
- int j = 0,
- k = -1,
- next[] = new int[pattern.length()];
- next[0] = -1;
- while (j < pattern.length() - 1) {
- if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
- j++;
- k++;
- if (pattern.charAt(j) != pattern.charAt(k)) // pj!=pk,有k个相同前缀和后缀子串
- next[j] = k;
- else {
- next[j] = next[k]; // pj=pk,则下次模式串从pnext[k]开始进行比较
- }
- } else {
- k = next[k];
- }
- }
- return next;
- }
- public static void main(String[] args) {
- String target = "abcadbabcab",
- pattern = "abcab";
- System.out.println(KMP.indexOf(target, pattern));
- }
- }
如果还不能很深刻理解 KMP,建议大家看一下 数据结构(Java 版)(第四版)(叶核亚)这本书 P79-P84, 笔者很大部分参考了这本书。
或者访问这个博客,http://www.cnblogs.com/SYCstudio/p/7194315.html 笔者觉得这个博客的作者画的动图更能加深认识。
来源: http://www.cnblogs.com/wang118/p/7229119.html