欢迎大家来到IT世界,在知识的湖畔探索吧!
KMP算法是一种高效匹配模式串的字符串匹配算法，时间复杂度只有O(N)，远比暴力匹配要高效的多，这里详细讲解一下KMP算法的原理，喜欢这篇文章的同学们请点赞 + 关注，你们的支持是我创作最大的动力！
首先KMP算法需要一个数组，数组的名字叫next，也叫前缀数组，是用来存储模式串的最长前后缀的数组，而且是真前后缀。
真前缀指的是除了最后一个字母以外，从第一个字母开始，下标连续的字符串，我们叫真前缀。而真后缀跟真前缀正好相反，除了第一个字母，从第二个字母开始，下标连续的字符串，叫真后缀，比如在一个模式串ABC中，A和AB都模式串的真前缀，C和BC都是模式串的真后缀。
那什么是最长前后缀呢？比如AAA，A和AA都是它的真前缀和真后缀，而AA是最长的，所以AA就是它的最长前后缀。
现在开始处理next数组，比如我有一个模式串：ABA，第一个A必然是忽略掉的，值为0。我们从第二个开始计算。
第二个是B，前面是A，A和B不相等，所以第二个字母的最长前后缀长度就是0。
第三个是A，第一个也是A，相等了，长度加一变成1。而AB和BA不相等，所以这不是相等的前后缀，最长前后缀就是1，所以ABA的next数组就是[0, 0, 1]。
有的人可能不解，这有什么用呢？这用处就是为了防止字符串回溯用的，回溯的意思就是在扫描的时候往回扫描了，这很影响匹配效率，但如果是模式串回溯就无所谓了，只要别让字符串回溯就行。为什么有了next数组字符串就不会回溯的呢？比如我有一个字符串ABCABA，要匹配ABA。
匹配第一个字母，A和A比较，相等，next下标加一等于1。
匹配第二个字母，B和B比较，相等，next下标加一等于2。
匹配第三个字母，C和A比较，不等，模式串下标到0的位置，也就是1 – 1。没错，next对应的元素减一就是要回溯到的位置。当然如果next对应的元素是0的话就直接回溯到模式串下标为0的位置就可以了。
匹配第四个字母，A和A比较，相等，next下标加一等于1。
匹配第五个字母，B和B比较，相等，next下标加一等于2。
匹配第六个字母，A和A比较，相等。next下标大于等于模式串长度减一，匹配成功！
从开始到结束，只有模式串在回溯，字符串没有回溯，这就是时间复杂度为O(N)的算法效果。
当然如果在匹配的过程中，字符串剩余的长度比模式串长度要短的话就可以直接结束了，不可能再匹配成功了。
本人算法水平不高，如果有错误的请指出，非常感谢支持我的创作！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/33926.html
