问题描述
指定文本串：aabaabaaf和模式串：aabaaf
使用KMP算法判断模式串是否在文本串中出现过？
假定模式串的长度小于文本串
思路解析
BF算法的问题是：模式串已经匹配到最后一位了发现不一样，需要将文本串和模式串的指针都往后退，导致有很多的重复匹配，效率很低。
KMP算法的思路是，在发现某个字符不匹配的时候，充分利用前面已经匹配过的结果，不要把“搜索指针”回退到已经比较过的位置，而是把模式串往后移动到合适的位置继续比较。KMP算法只需要对文本串搜索一次，时间复杂度是O(n)。
检索过程图解
image
如上图所示，在遇到不匹配的时候，依靠“部分匹配表”可知，最后一个匹配字符a对应的部分匹配值是2，可以根据下面的公式计算出模式串的移动位数。
移动位数 = 已经匹配的字符串长度 - 对应的部分匹配值
aabaa是已经匹配的字符串，长度是5；aabaa对应的部分匹配值是2，因此将模式串往右移动3位，就可以继续匹配了，KMP就是通过这个“部分匹配表”避免了搜索指针的回退。
部分匹配表
要理解部分匹配表，需要了解两个概念：前缀子串、后缀子串
- 前缀子串：包含首字母，不包含尾字母的所有子串
- 后缀子串：包含尾字母，不包含首字母的所有子串
例如：单词"bread"
- 前缀子串："b","br","bre","brea"
- 后缀子串："d","ad","ead","read"
部分匹配表中的数值含义是：当前这个字符前面的字符串中，相等的前缀子串和后缀子串的最大的长度。计算下aabaa的部分匹配表：
- a：前缀子串集合和后缀子串集合都是空集，相等的前后缀子串的最大长度是0
- aa：前缀子串集合是[a]，后缀子串集合是[a]，相等的前后缀子串的最大长度是1
- aab：前缀子串集合是[a,aa]，后缀子串集合是[b,ab]，相等的前后缀子串的最大长度是0
- aaba，前缀子串集合是[a,aa,aab]，后缀子串集合是[a,ba,aba]，相等的前后缀子串的最大长度是1
- aabaa，前缀子串集合是[a,aa,aab,aaba]，后缀子串集合是[a,aa,baa,abaa]，相等的前后缀子串的最大长度是2
- aabaaf，前缀子串集合是[a,aa,aab,aaba,aabaa]，后缀子串集合是[f,af,aaf,baaf,abaaf]，相等的前后缀子串的最大长度是0
“部分匹配表”的实质是，模式字符串中有时会有重复的子串，例如：aabaa的左右两边都有aa，那么该字符串的部分匹配值就是2，那么在发现aabaaf中的f不匹配的时候，只需要将aabaaf这个模式串往右移动3个位置，就可以让第一个aa来到第二个aa的位置。
image
代码实现
package org.javaadu.string;
import java.util.List;
public class StringSearchDemo {
public static void main(String[] args) {
String text = "aabaabaaf";
String pattern = "aabaaf";
boolean kmpRes = kmpSearch(text, pattern);
System.out.println("kmpRes:" + kmpRes);
}
/**
* 利用KMP算法求解pattern是否在text中出现过
*
* @param text 文本串
* @param pattern 模式串
* @return pattern在text中出现，则返回true，否则返回false
*/
public static boolean kmpSearch(String text, String pattern) {
//部分匹配数组，就是很多算法实现中的next数组
int[] partMatchTable = buildPartMatchTable(pattern);
//text中的指针
int i = 0;
//pattern中的指针
int j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
//字符匹配，则两个指针同时后移
i++;
j++;
} else if (j > 0) {
//字符失配，则利用next数组，异动j指针，避免i指针回退
j = partMatchTable[j - 1];
} else {
//pattern中的第一个字符就失配了
i++;
}
if (j == pattern.length()) {
//搜索成功
return true;
}
}
return false;
}
private static int[] buildPartMatchTable(String pattern) {
//初始化
int[] partMatchTable = new int[pattern.length()];
int prefixLen = 0;
next[0] = 0;
int i = 1;
while (i < pattern.length()) {
//pattern[prefixLen]，表示目前最长相等子串的最后一位
//pattern[i]，表示目前正在处理的子串的最后一位的字符
if (pattern.charAt(prefixLen) == pattern.charAt(i)) {
//如果它俩相等，说明找到了更长的相等子串
prefixLen++;
partMatchTable[i] = prefixLen;
i++;//处理下一个i的字符
} else {
//如果不相等，则需要尝试下更短1位的子串是否满足要求，因此这里要把再次循环尝试下：仅仅改变prefixLen的值，不改变i的值
prefixLen = next[prefixLen - 1];
if (prefixLen == 0) {
//如果实在没有合适的，则说明当前正在处理的子串的最长相等前后缀的长度是0
partMatchTable[i] = 0;
i++;//处理下一个i的字符
}
}
}
return partMatchTable;
}
}
参考资料
- https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
- https://www.bilibili.com/video/BV1AY4y157yL/?vd_source=a7cf54b1d9550c0b692539a82b982181
- https://www.bilibili.com/video/BV1PD4y1o7nd/?spm_id_from=333.337.search-card.all.click&vd_source=33b7a49ff9ee993637d7533b74ed12a5
网友评论