字符串匹配算法之KMP

绝地灬酷狼 2023-03-01 08:37 23阅读 0赞

### 目录 ###

*  需求
 *  基础知识
 *  逻辑解析
 *  源码实现

# 需求 #

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

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

解决方案一：  
大家常用的方式可能是if()\{continue;\} esle if ()\{continue;\} …或者switch-case等;

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

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

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

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

例如：

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

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

# 基础知识 #

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

KMP算法解决的问题：在字符串（主串）中是否能够定位出模式串（子串）。  
上面提及到暴力匹配字符串，为什么不使用呢？时间复杂度O(m\*n),而KMP算法时间复杂度为O(m+n)。

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

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

简单举例：

字符串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。

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

<table> 
 <thead> 
  <tr> 
   <th>搜索串</th> 
   <th>A</th> 
   <th>B</th> 
   <th>C</th> 
   <th>D</th> 
   <th>A</th> 
   <th>B</th> 
   <th>D</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>部分匹配值</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

# 逻辑解析 #

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

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

移动位数=已匹配的字符数-**最后一个匹配字符**对应的部分匹配值  
因此，第5点之后，主串中空格与P串字符D字符不匹配时，已匹配字符为6个，最后一个以匹配字符B对应的**部分匹配值**为2，因此P串应该移动的位数为6-2=4。如图：  
![在这里插入图片描述][20200722223420728.png]  
8. 空格与字符Ｃ不匹配，因此P串继续往后移。计算移动位数：已匹配的字符数为2（“AB”），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2。  
![在这里插入图片描述][20200722223649344.png]  
9. 空格与A不匹配，继续后移一位。  
![在这里插入图片描述][20200722223851780.png]  
10. 逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。  
![在这里插入图片描述][20200722223954823.png]  
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/

[20200722220804107.jpg]: /images/20230209/329fcdab699c41219079b65854630dbf.png
[20200722220937870.jpg]: /images/20230209/77ba76d0059a4a40b513474243dcb8ca.png
[20200722221300138.png]: /images/20230209/683edfdff647476da8bfa4f328bd6cd7.png
[20200722221521122.png]: /images/20230209/1c4e0568721c4c7799834e4528614f71.png
[20200722221656663.png]: /images/20230209/586befaeb28743988bb5a52db9e45c1a.png
[20200722221904908.png]: /images/20230209/920cf96da3d84e45abf1c8077caf7095.png
[20200722223420728.png]: /images/20230209/31e0b606b1bf4aa7b1e0f2533930d625.png
[20200722223649344.png]: /images/20230209/33a2083c225a42b8ae0dba36b0ebd33b.png
[20200722223851780.png]: /images/20230209/a49a0a44a32948f88f3af133a70086e9.png
[20200722223954823.png]: /images/20230209/b7a34605b20948ce98e53d68979e32c1.png