带你从过程理解KMP算法

分手后的思念是犯贱 2024-05-01 16:01 77阅读 0赞

简介：

KMP算法是一种针对字符串匹配的一种改进算法，D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此叫KMP算法

字符串匹配，我们会怎么做？

长字符串L：abababzabababa

短字符串S：abababa

1.  先比较L\[0\] == S\[0\]，相等的话对应下标各加一，继续比较L\[1\] == S\[1\].....，
2.  当L\[i\] !=S\[i\]时，L的下标回退到第2个字符，S的下标退回到第一个字符，按照步骤1重新比较
3.  每次遇到L\[i\] !=S\[i\] ，L就回到当前循环的开始下标 +1 ，S从头开始匹配

这样固然可以得到结果，但是有没有更好的方法呢？KMP算法的作者们考虑到，如果每次循环匹配失败后，不用回到起始下标的后一个，而是回到中间某个位置，就能简化算法，下满我们一起来看一下KMP产生的历程；

长字符串L：a b a b a b z a b a b a b a

短字符串S：a b a b a b a

1 2 3 4 5 6 7

1.  第一次查询的过程，在第7个字符比较时，发现了不匹配，也就是说，前6个字符都是匹配的,即L6 (L的前6个字符)= ababab
2.  那么后面的匹配，S的头部必然在长字符串的前6个字符串中的尾部，占k个连续字符（0<=k<6,因为k==6的情况在第一次查询的时候已经验证为不匹配），这里如果有不清楚的可以想一下旧的匹配过程。
3.  那么k究竟是多少呢？
4.  要研究出k究竟是多少，我们先来分析一下这k个字符的和L、S的特征。
5.  S的头部连续k（0<=k<6》）个字符，和L6(L的前6个字符)的后面连续k（0<=k<6》）个字符是相匹配的，k == 1时，a 和 b；k == 2时，ab 和 ab；k == 3时，aba 和 bab；k == 4时，abab 和 abab；k == 5时，S的头5个字符： ababa 和L6的后5个 字符：babab不匹配，所以 k == 2,4;（k标示长度）
6.  想要找到所有匹配的字符串，那么起始位置尽量靠前（所以我们一般的做法是从上次循环的起始点+1），同时又去除掉一定不会匹配成功的循环（上面五步分析的）,根据匹配特点，第2次的匹配中，S的前k个字符必然和L6的后k个字符匹配，所以k是满足条件的尽量大，起始点才回尽量往前
7.  所以k == 4 ，第二次循环从L的第（1 + 6 - 4）【1代表上次循环开始的是第几个字符】个字符（L\[0+6 - 4\]）【0代表上次循环开始的字符的下标】开始比较，又因为，上面所说， k（k == 4）0个字符已经匹配过了，即，L从L\[6 - 4\]到L\[5\] 确定是和S的前4个相匹配的，所以，第二次的比较直接从L\[6\] 和S\[4\] 开始比较（可以看出，如果上次匹配到第7个字符失败，找到前六个字符的 k 后，第二次比较的是 从L的第7个字符(L\[6\])和S\[K\]开始的）
8.  有小伙伴问，第2次，z和a还是不匹配，参考上诉 只是 6 变成了4 ababab（abab）变成了 abab（ab） ，k 从4变成了2
9.  这是聪明的小伙伴可以根据上面的逻辑联想到 ababab 和 abab具有一定的关系 ，abab是从ababab中获取的，那么下次就该从abab中获取 ，会获取到ab；abab也是L的前4个字符

S的 前m个字符，对应的最大k ，其实就是这m个字符的前k个与后k个是匹配的，我们称为最大真前缀 和最大真后缀，每个对应的k是关键，我么称k为最大匹配数

短字符串S： a b a b a b x a b a

短字符串S： a b a b a b x a b b

最大匹配数：0 0 1 2 3 4 0 1 2 ?

? 应该是几 前面的最大匹配数是 2 那么 如果 ？对应的 a与S的第三个一致，就是2+1；如果不一致，就不能这么算了；？前面的2代表除去最后一个字符，最大k为2，即 ab ，因为最后一个和第三个（S\[2\]）不一致，那么需要看ab的次小的字串 也就是 前两个字符对应的最大匹配数 0， ？对应的字符和S\[0\]比较，不一致，所以？为0；

所以构造S的各个字符最大K的方法为：

public static int[] maxMatchLengths(String s) {
    	    int[] maxMatchLengths = new int[s.length()];
    	    int maxLength = 0;
    	    for (int i = 1; i < s.length(); i++) {
    	    	
    	        while (maxLength > 0 && s.charAt(maxLength) != s.charAt(i)) {
    	            maxLength = maxMatchLengths[maxLength - 1]; 
    	        }
    	        if (s.charAt(maxLength) == s.charAt(i)) {
    	            maxLength++; 
    	        }
    	        maxMatchLengths[i] = maxLength;
    	    }
    	    return maxMatchLengths;
    	}

之后获取匹配结果的代码：

public static List<Integer> search(String l, String s) {
    		    List<Integer> positions = new ArrayList<>();
    		    int[] maxMatchLengths = maxMatchLengths(s);
    		    int count = 0;
    		    for (int i = 0; i < l.length(); i++) {
    		        while (count > 0 && s.charAt(count) != l.charAt(i)) {
    		            count = maxMatchLengths[count - 1];
    		        }
    		        if (s.charAt(count) == l.charAt(i)) {
    		            count++;
    		        }
    		        if (count == s.length()) {
    		            positions.add(i - s.length() + 1);
    		            count = maxMatchLengths[count - 1];
    		        }
    		    }
    		    return positions;
    		}

总结：S的前后缀匹配越多，就越快，如果是abcdefg这种，其实就和咱们最开始的想法计算的复杂度差不多了