谢尔顿的左耳朵www.zhangxiaoshuai.fun
你可能听过KMP这个名词，先不用管KMP是什么，看看下面的问题：
给你一个字符串”jail“，让你在“abjacalisjaisnfljailnafa”中寻找该字符串是否存在。
第一次看到这道题的时候，上来就是一通暴力匹配，思路也很容易理解
该题暴力解法的基本思路是：用两个指针分别指向字符串P和T的首个字符
- 如果指针指向的字符相同，那么两个指针同时后移
- 一旦两个指针指向的字符不同，字符串T的首个字符和P中的下一个位置重新开始匹配
重复上述两个步骤，直到两个指针任意一个指针走到了字符串的结尾，循环截止；
如果T的指针的大小等于T的长度，说明匹配成功，否则，匹配失败。
问题是可以解决，但是，其中很多步骤都是重复的，因为一旦匹配失败，T字符又要从头开始匹配，这样是不是浪费了很多时间？
而生活中我们使用字符串匹配的地方是非常多的
我们所用的IDE、office办公软件、文本编辑器等等非常多的软件中是不是都包含了文本查找、文本替换这些功能呢？
这个时候，KMP算法横空出世
图片中的内容截取于维基百科
说了这么多，这个算法究竟是如何进行字符串查找的呢？
首先，该算法需要在开始匹配之前收集足够的“信息”，用于在匹配过程中给出“指导意见”
这个“信息”指，根据待查找字符串T建立的一张表
但是最长公共前后缀长度如何求呢？
如果长的字符串不容易得出答案，那我们尝试从最短的字符串看看：
a：很明显，它的公共前后缀长度为0
ab：公共前后缀长度为0，因为a != b
aba：公共前后缀长度为1，也是最长的，因为前后都有一个a
abab：最长公共前后缀长度为2
ababc：最长公共前后缀长度为0
比较aba和abab，你能发现什么？
在aba的基础上加了一个字符，这个字符和第一个a后面的字符相同，所以在aba的基础上，abab的最差公共前后缀长度为2
而在abab的基础上加了一个c字符，整个字符串的公共前后缀的长度就变为了0，这是因为c字符和abab中的任何字符并不相等
发现规律了嘛？
从最小的开始比较，因为当一个字符作为子串的时候，公共前后缀的长度一定是0，就不用计算了，从第二个开始，也就是从ab开始，我们比较0位置和1位置是否相同，相同的话最长公共前后缀就是1，否则就为0
然后继续看aba，比较新添加的字符和上一次求出的公共前后缀长度值的位置的字符是否相同，相同，用求出的上一个子串的公共前后缀长度加上1，aba的最长公共前后缀长度就为1
abab，还是上述步骤，看新添加字符和第[上一个子串的最长公共前后缀长度]个字符，也就是1位置和3位置，相同，那么abab子串的最长公共前后缀长度=1+上一个子串的最长公共前后缀长度
那么如何根据这个表来进行加速匹配呢？
匹配的过程中一定是按照相应的规则进行匹配的，对应的，table中的值可是大有用处的，先不说那么多概念，最直观的感受一下KMP算法是如何进行匹配的吧
上面的动画中，我们让字符串T在字符串P中进行匹配，如果在P中找到了T的存在，返回true，否则返回false；
匹配的规则还是一个字符对一个字符进行匹配，但是KMP算法神奇的地方就在于，当两个字符没有匹配成功的时候所采取的策略，这个策略并不是和暴力解法那样：一旦一个字符没有匹配成功，不管之前有多少个匹配成功，直接从头再来。
这个策略依托的就是我们最开始建立的最长公共前后缀表
- 两个字符匹配的时候，相安无事，两个指针都往后移动；
- 一旦两个字符没有匹配成功，首先要做的就是拿到T指针的位置在table表中找出对应位置的值，这个值就是我们下一次要进行匹配的T字符串中起始位置
代码：
public boolean kmp(String resource, String target) {
int len = target.length();
if (len < 1) return false;
//确定最长公共前后缀表
int[] preTable = new int[len];
commonPrefix(target,preTable);
int i = 0,j = 0;//i指向resource j指向target
while (i < resource.length() && j < target.length()) {
//如果两个指针指向的字符不同
if (resource.charAt(i) != target.charAt(j)) {
//根据最长公共前后缀表中j所在位置的值移动指针
//如果小于0，resource中的指针后移，j不动
if (preTable[j] < 0) {
i++;
} else {
//否则将指针j的位置修改为最长公共前后缀表中j位置对应的值（重新确定匹配位置）
j = preTable[j];
}
} else {
i++;
j++;
}
}
//如果指针j的长度等于target长度说明匹配成功，否则，失败
return j == target.length();
}
//获取target字符串的最长公共前后缀表
private void commonPrefix(String target, int[] preTable) {
int n = target.length() - 1;
if (n > 0 && n < 2) {
preTable[0] = -1;
return;
}
//为了编码方便
preTable[0] = -1;
//一个字符的最长公共前后缀长度一定是0
preTable[1] = 0;
int index = 2;
int j = 1;
while (j < n) {
if (target.charAt(preTable[index - 1]) == target.charAt(j)) {
preTable[index] = preTable[index - 1] + 1;
} else {
preTable[index] = 0;
}
index++;
j++;
}
}
感谢大家的阅读，如果对文中内容有不同见解，希望不吝赐教。
今天的文章c++中比较两个字符串比较的是什么大小_GIF警告!让你搞懂到底什么是KMP算法分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/64167.html
