KMP算法的及其原理

落日映苍穹つ 2023-10-14 08:26 35阅读 0赞

KMP算法

首先 我们先了解一下 KMP算法的作用 str1 和str2 字符串 如果str1中包含str2 那么返回头位置

如果不包含返回-1

首先 我们先加入一个概念: 有一个next数组 next\[i\]的值为 str2 中 以i-1位置为结尾的字符串中 最长相同前缀后缀为多长(相同前缀后缀 不是对称 aba 中相等的后缀为a 而非ab ba(这个是对称) 且不要让前缀\\后缀长度等于字符串 因为对于任何一个字符串来说 它本身的最长前缀/后缀都是它本身 肯定相等)

举个例子 a b a b f f位置的next值为2 0 1 位置的next值恒为-1

好 来开下流程 str2先匹配str1 两个指针齐头并进 到达第一个不满足的位置 它位置的next值为5 那么直接从str2的5位置接着匹配下去

![a32c62bf006746a18a8ebf01ac0f800a.jpeg][]

就是从这个X Y为不同的地方 然后str2 Z和str1 Y继续匹配 如果再不相同呢 就找到Z 的next答案 然后从答案位置匹配... 如果一直next到0了 都没匹配成功 那就让str1的指针++ 也就是说从Y+1为开头继续匹配

解释一下原因

![e7fc136a62614af08f935cbc16bc6a7c.jpeg][]

首先我们知道Z和Y匹配 本质上是看以N开头的字符串和整个str2匹配 但是为什么N到Y之间的那段不用看了呢 首先对于str2来说 因为X位置的答案为5 那么str2的前五个(0-4)和后五个一定相等对吧 然后因为我们str1和str2 X Y之前的部分已经判断完相等了对吧 所以str2的0-4 等于 (x-5)~(x-1) 然鸡皮N~Y-1 又和 (x-5)~(x-1)一一对应 所以0-4和N~Y-1 就一定相等

那为什么不能是本质上N+1和0位置上匹配呢 额 因为X Y位置不同了 所以他到这一定会断掉

哎 是不是感觉还有哪不对 是的 这只能解释 N到Y-1的部分不用判断 但是解释不了为什么N之前的不用判断

好 我们假设N之前有匹配的字符串

![12a50b7aea5d453e8c53ce2b915c120b.jpeg][]

对吧 假设S位置就可以匹配上了 那str2的前八个字符肯定和这个S开始的八个字符相同 再因为Y前的字符和X前的字符一 一相等 所以 S到Y-1 一定和下面str2中X-8到X-1的字符一 一对应 那也可以推出对于str2来说0~7和X-8到X-1相同 那X位置的next值应该是8啊 怎么能是5呢 这就冲突了 对不对

所以基于这两个原理 str2可以直接和N进行比较

然后看做一个递归过程 如果我Z和Y没匹配上 那是不是又是一个同样的问题 哎 再去找Z的答案 一直找 找到str2开头0位置了 还没找到 那就说明真配不上 这整个一块都不行 你就把Y往下走吧

快速求next数组

反正跳出的时候 cn一定是当前位置的值 那到下一个循环的时候 cn就一定是上一个位置的结果 那str\[cn\]对应的是什么呢 就是要判断的位置啊  
因为next的值是前缀后缀相同的长度 如果这个位置的值是2 好 那我们就要判断第三个元素相不相同 如果相同 那就是值就是2+1 其实本来应该是前缀长度+1的位置的 但是正好 数组是从0开始的 都省了

那如果这个位置不同呢? 那就说明衔接不上 那我们再往前推一段

假如说a b a s a b a t g 这个数组 它对应位置的值为(是相等 不是对称)

\-1 0 0 1 0 1 2 3

我们求g g位置本质是求t结尾的前缀后缀相同最大长度 a结尾的最大相同长度为3 哎 如果我这个t正好和第四个位置相同 是不是就直接套上了 可惜不同 那没办法 但是呢 也不一定直接为0 还要看我们3位置的值 因为你不能接在这个后面的话 那更短的位置呢

假如这种情况 abagababs 我们求s位置的值 也就是以前一个字符结尾的那个值 虽然部门不能接到aba后面让最大相等长度为4 但是我们可以去看更前面 它和ab还是组成了前缀 后缀相同的

画个图直观理解一下

![b9214a2b726043cbbcbd73d17f61c927.jpeg][]

Y位置的结果 就是以Y-1结尾的最长相等前缀后缀 假如说已经求出来了 这两个方块区间代表 前缀和后缀 我们求Y+1的结果 那就是以Y结尾的最长相等前缀后缀 这两块区间肯定相等的 如果Y和X相等 那是最好的 我们直接上一个位置的值+1 就出结果了 但是不同呢?难道直接归零去比对吗 不 还可以优化

假如说x位置有值 这个值 就代表着前缀a 前缀b是相等的 那么在x的另一侧就有对应的 c 和d 相等

因为根据Y知道 x的左右两个大区间肯定是相等的

所以可以推出a和c相等 b和d相等

有了这几个条件 我们就知道了 a和d相等 所以Y如果和a的下一个字符配上了 那它的结果就等于x结果加1

![81dcba680b0c41b4b632204cdbcbcc68.jpeg][]

那一直干到最开始都没匹配上 那就说明 没有了呗

OK我们开始coding

public static int KMP(String str,String match) {
    		char [] str1 = str.toCharArray();
    		char [] str2 = match.toCharArray();
    		int x = 0;
    		int y = 0;
    		int [] next = getnext(str2);
    		while(x<str1.length&&y<str2.length) {
    			if(str1[x]==str2[y]) {
    				x++;
    				y++;
    			}else if(next[y]==-1){
    				x++
    			}else {
    				y = next[y];
    			}
    		}
    		return y == str2.length ? x - y : -1;//y走到头了 说明匹配出来了(y要比实际位置+1 走出while循环都这样) x走到头了说明没有
    	}
        public static int [] getnext(char [] str) {
    		int [] next = new int [str.length];
    		next[0] = -1;
    		next[1] = 0;
    		int index = 2;
    		int cn = 0;
    		while(index<str.length) {
    			if(str[index-1]==str[cn]) {
    				next[index++] = ++cn;
    			}else if(cn>0) {
    				cn = next[cn];
    			}else {
    				next[index++] = 0;
    			}
    		}
    		return next;
    	}

[a32c62bf006746a18a8ebf01ac0f800a.jpeg]: https://img-blog.csdnimg.cn/a32c62bf006746a18a8ebf01ac0f800a.jpeg
[e7fc136a62614af08f935cbc16bc6a7c.jpeg]: https://img-blog.csdnimg.cn/e7fc136a62614af08f935cbc16bc6a7c.jpeg
[12a50b7aea5d453e8c53ce2b915c120b.jpeg]: https://img-blog.csdnimg.cn/12a50b7aea5d453e8c53ce2b915c120b.jpeg
[b9214a2b726043cbbcbd73d17f61c927.jpeg]: https://img-blog.csdnimg.cn/b9214a2b726043cbbcbd73d17f61c927.jpeg
[81dcba680b0c41b4b632204cdbcbcc68.jpeg]: https://img-blog.csdnimg.cn/81dcba680b0c41b4b632204cdbcbcc68.jpeg