字符串匹配算法之KMP

需求

先简单描述溪源曾经遇到的需求：

需求一：项目结果文件中实验结论可能会存在未知类型、转换错误、空指针、超过索引长度等等。这里是类比需求，用日常开发中常出现的错误类型作为需求，如果要以上结论则判断这个项目检测失败；

方案二：可能会使用集合contain()方法;

方案三：依次匹配字符串中字符（暴力匹配）；

以上两种方案都能解决；然后大家需要考虑性能、维护和代码整洁性，可能居多使用方案二；

需求二：项目结论中即存在正常、成功的结论，又存在以上列举的失败字段；

例如：

//存在异常错误 String str1 = "正常范围内;转换错误"; //存在异常错误 String str2 = "i=20空指针;超出索引长度;j正常"; //正常值 String str3 = "i=30;j值正常"; ...等等 

面对这种需求，大家可能会想到split()方法之后再判断是否正常等等…相信大家总是会有办法解决的。不再列举了，面对产品经理各种需求大家尽情发挥脑洞吧，那么开始进入今天的正题，溪源采用KMP字符串匹配算法解析此需求。

基础知识

根据上面介绍的需求，大家应该会对KMP算法解决的问题稍有理解。

再介绍几个概念性的知识：

• 前缀：除最后一位以外，第一位依次与其余字符组成的字符串集合；
• 后缀：除第一位以外最后一位依次与其余字符组成的字符串集合；

简单举例：

字符串ABCD，其前缀：A,AB,ABC; 后缀：BCD,CD,D

• 部分匹配值：子串的前缀和后缀共有元素的长度。

简单举例：列举字符串ABCDABD的各个子串公共元素长度如下：

 -　"A"的前缀和后缀都为空集，共有元素的长度为0； 　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0； 　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； 　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； 　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1； 　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2； 　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。 

综上可以得出下面的表格：

逻辑解析

经历过上面的基础知识介绍后，下面开始一步步逻辑解析整个匹配过程：

1. 字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索串（模式串，以下简称P串）”ABCDABD”的第一个字符，进行比较。
   
   
2. 由于B与A字符不匹配，P串整体再往后移动一位与主串比较。
   
   
3. 此时主串第二位字符B与搜索串第一位A依然不匹配，P串再继续移动…，直至主串存在与P串第一个字符匹配。
   
   
4. 依次比较P串与主串的字符是否匹配。
   
   
5. 匹配过程中存在与主串存在不匹配字符。
   
   
6. 此时，大家应该是将P串再次整个后移一位，再从头逐个比较，如下图所示。虽然此种方式有效，但是效率很差，因为要把”搜索位置”移到已经比较过的位置，再次重比一遍。
   
   
7. 从5点可以明确知道，P串中字符D与主串空格不匹配时，其实字符D之前已经匹配的六个字符是已知的。因此KMP算法思想就是利用这个已知信息，不要重复比较已经比较过的位置，而是继续将P串向后移动几位。
   重点来了，向后移动几位呢？此时便用到了上面介绍的部分匹配表。
   

移动位数=已匹配的字符数-最后一个匹配字符对应的部分匹配值
因此，第5点之后，主串中空格与P串字符D字符不匹配时，已匹配字符为6个，最后一个以匹配字符B对应的部分匹配值为2，因此P串应该移动的位数为6-2=4。如图：

8. 空格与字符Ｃ不匹配，因此P串继续往后移。计算移动位数：已匹配的字符数为2（“AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 – 0，结果为 2。

9. 空格与A不匹配，继续后移一位。

10. 逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 – 2，继续将搜索词向后移动4位。

11. 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 – 0，再将搜索词向后移动7位，这里就不再重复了。

源码实现

public class Kmp { 
    / * * @param originString 源字符串 * @param subString 子串 * @param next 部分匹配表, 是子串对应的部分匹配表 * @return 如果是-1 就是没有匹配到，否则返回第一个匹配的位置 */ public static int kmpSearch(String originString, String subString, int[] next) { 
    for (int i = 0, j = 0; i < originString.length(); i++) { 
    while (j > 0 && originString.charAt(i) != subString.charAt(j)) { 
    j = next[j - 1]; } if (originString.charAt(i) == subString.charAt(j)) { 
    j++; } if (j == subString.length()) { 
    return i - j + 1; } } return -1; } / *获取到一个字符串(子串) 的部分匹配值表(前缀、后缀共同元素的长度) * @param dest 子串 * @return */ public static int[] kmpNext(String dest) { 
    //创建一个 next 数组保存部分匹配值 int[] next = new int[dest.length()]; //如果字符串是长度为 1 部分匹配值就是 0 next[0] = 0; for (int i = 1, j = 0; i < dest.length(); i++) { 
    while (j > 0 && dest.charAt(i) != dest.charAt(j)) { 
    j = next[j - 1]; } //当 dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1 if(dest.charAt(i) == dest.charAt(j)) { 
    j++; } next[i] = j; } return next; } public static boolean matcherResult(String originString, List<String> unknownList) { 
    boolean unknown = false; for (String unknownConclusion : unknownList) { 
    int[] kmpNext = kmpNext(originString); int index = kmpSearch(originString, unknownConclusion, kmpNext); if (index != -1) { 
    unknown = true; break; } } return unknown; } } 

参考资料：http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/