大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
需求
先简单描述溪源曾经遇到的需求：
需求一：项目结果文件中实验结论可能会存在未知类型、转换错误、空指针、超过索引长度等等。这里是类比需求，用日常开发中常出现的错误类型作为需求，如果要以上结论则判断这个项目检测失败；
解决方案一：
大家常用的方式可能是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。
综上可以得出下面的表格：
| 搜索串 | A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|---|
| 部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
逻辑解析
经历过上面的基础知识介绍后，下面开始一步步逻辑解析整个匹配过程：
- 字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索串（模式串，以下简称P串）”ABCDABD”的第一个字符，进行比较。
- 由于B与A字符不匹配，P串整体再往后移动一位与主串比较。
- 此时主串第二位字符B与搜索串第一位A依然不匹配，P串再继续移动…，直至主串存在与P串第一个字符匹配。
- 依次比较P串与主串的字符是否匹配。
- 匹配过程中存在与主串存在不匹配字符。
- 此时，大家应该是将P串再次整个后移一位，再从头逐个比较，如下图所示。虽然此种方式有效，但是效率很差，因为要把”搜索位置”移到已经比较过的位置，再次重比一遍。
- 从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/
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/171695.html原文链接：https://javaforall.net
