KMP算法
概述
- KMP问题：字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中的开始位置，如何做到时间复杂度为O(n)
- 常规思路：从str1的头的尾的字符依次作为str2的开头进行测试，时间复杂度为O(N * M)，N：为str1的长度，M：为str2的长度
- KMP方法的比较方式借鉴了常规方法只是在常规方法的基础上进行加速，每一次比较的出发点可以根据上一次比较得到的数据进行优化，减少比较次数，从而在时间复杂度上进行提升
KMP思路
- 最长前缀与后缀的匹配长度：在不取到前后长度完全相同之前时，前后缀相同能达到的最大长度
如上图：k的下标为3 - nextArr数组：对str2求对应所有字符的最长前缀与后缀匹配长度，规定：0位置为 -1；1位置为 0
- str1从 i 位置与str2比较，在str1的x位置与str2的y位置发生不匹配现象
常规思路：str1中x位置跳回 i + 1位置，str2中y位置跳回 0 位置，重新开始比较
KMP思路：得到y位置对应nextArr数组的值，找到y匹配度前面相同的一截；将str1停留在x位置（KMP中str1的x位置只会往后走，绝对不会在退到前面重新比较），str2由y位置移动到前面相同位置的后一位，开始比较
- 解析：因为nextArr，str2中有两段相同，在str1的 j 位置开始是与str2中的后缀相同的，所以可以直接将str2从str1 的 i 位置推到 j 位置，又因为前后缀相同直接从str2前缀相同的下一位与str1的 x位置进行比较
- 例：str1 的 e 与 str2 的 w不相等
第一次跳跃：找到str2的w 位置的nextArr数组对应的值，此时str2 的 t 位置与str 1的 e位置开始比较，相当于：将str2移动到str1中第二个框住 a的位置比较，又因为有一部分相同，所以是 t 位置与 e 位置的比较
第二次跳跃：t 与 e 又不相同，找到str2的t位置的nextArr数组对应的值，str2 的s位置与 str1的e位置比较
第三次跳跃：s 又与 e不同，此时s的nextArr为0，则跳回str2的开头位置与 e 比较，还是不同，将str1到e的下一个位置，重新开始
代码实现
- nextArr数组的求法
（1）0位置：-1，1位置：0
（2）x位置是：n，若x位置与前缀的下一个位置相同，则x + 1位置就是：n + 1；若x位置与前缀的下一个位置不同，前缀下一个位置为：m，就跳到前缀的前缀，若相同，则x + 1位置就是：m+ 1，若不同继续先前找前缀……直到找到最前面若x与最前面相同， x + 1位置就是：1，不同就是0 - 例：
x 的nextArr位置为8，确定 x + 1的nextArr位置就是又x的值决定
（1）若 x 为 e，则 ? 为 x 的nextArr + 1，为 9
（2）若 x 不为 e，就跳到 s 与其比较，若相同 ? 是 e 的nextArr + 1为 4
（3）若 x 不为 s，就跳到最前面 a 比较，若相同 ? 是 s 的nextArr + 1为 1
（4）若 x 不为 a，就是 0
求解 next 数组 public static int[] getNextArray(char[] str) { if (str.length == 1){ return new int[] {-1}; } //默认，0位置是-1，1位置是1 int[] nextArr = new int[str.length]; nextArr[0] = -1; nextArr[1] = 1; int index = 2; //next数组的位置 int pre = 0; //要比较字符的位置（前缀的下一个）也有前缀长度的含义 while (index < str.length){ //时间复杂度为：O(M)，M = chs1.length if (str[index - 1] == str[pre]){ //index - 1 与 pre 位置相同 //nextArr[index] 就是上一个位置加一 //pre：前缀长度增加 nextArr[index] = nextArr[index - 1] + 1; index++; pre++; } else if (pre > 0){ //不相同，跳到上一个前缀进行比较 pre = nextArr[pre]; }else { //跳到了最前面，也不相同 nextArr[index] = 0; index++; } } return nextArr; }
kmp代码 public static int kmp(String str1, String str2){ //匹配成功，返回str1中匹配str2成功的位置，否则返回 -1 if (str1 == null || str2 == null || str1.length() < 1 || str2.length() < 1){ return -1; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int index1 = 0; int index2 = 0; int[] next = getNextArray(chs2); while (index1 < chs1.length && index2 < chs2.length){ //时间复杂度为：O(N)，N = chs2.length //若是因为index2 == chs2.length结束while，说明匹配成功 //若只是因为index1 == chs1.length结束while，说明整个匹配失败 if (chs1[index1] == chs2[index2]){ index1++; index2++; } else if (index2 == 0){ //等同与：else if (next[index2] == -1) //index2回到0位置，且str1仍不匹配，直接使index1移动 index1++; } else { //index2的跳跃，就是对应下标next数组中的值 index2 = next[index2]; } } //判断是否匹配成功 return index2 == chs2.length ? index1 - index2 : -1; }
