KMP详解

40bc3cb7697a13d587b80e33feb3dcc9.png

KMP的本质是通过已经掌握的而信息来规避重复的运算

只需要一次主串的遍历就可以完成匹配，next数组的存在让j的回溯不需要循环，而是提前准备好表备查，这样没有循环的嵌套，复杂度仅为O(n)

pattern a b c a b c
j 0 1 2 3 4 5
next -1 0 0 0 1 2

可以看出来，next数组存的是如果该位置匹配失败那么该跳到哪里，j=4如果匹配失败了，那么此时前后缀长度为1，应该回溯到j=1。这样的话，我们构建next数组的时候只需要把当前位置产生的前后缀信息放到下一个位置便可以了，也就是说，最后一个位置的前后缀信息是不用比较的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int indexOf(String target, String pattern){
    return indexOf(target, pattern, 0);//下一个写的是从固定位置开始比较，不写位置的话默认从0位置开始比较
}
public static int indexOf(String target, String pattern, int begin){
    int n = target.length(), m = pattern.length();
    if(begin<0)
        begin = 0;//begin容错
    if(n==0 || n<m || begin>=n)//目标串长度为0，目标串小与模式串，开始比较的位置bigin就已经越界，均不符合要求
        return -1;
    next = getNext(pattern);
    int i = begin,j = 0;
    while(i<n && j<m){
        //循环条件：i比到n，j比到m
        if(j==-1 || target.charAt(i)==pattern.charAt(j)){
            //比对成功可以让指针加1
            //也可能j是被回溯，然后再来比较，并且有可能直接被回溯为-1，如果回溯为-1，说明没有可以利用的子串信息，直接比下一对就行，所以也需要两指针+1
            //回溯到-1和0是不一样的，0还需要比较一下i和j=0两位置的字符，失败的那个位置没有可以用的子串信息，只能和第0号字符比较了，但是如果回溯到了-1，说明，第0号元素也不用比较了，这一次的匹配失败已经证明了和第0个肯定不相同，直接回溯到-1，就能在下一次循环中让两个指针+1，不用浪费一次比较
            i++;
            j++;
        }
        else{
            j = next[j];//匹配字符失败，j回溯
            if(n-i+1<m-j+1)//如果目标串长度还没子串长，那就不用比了
                break;
            
        }
    }
    return j==m?i-m:-1;
}

构建next

  1. k前缀长度一定是依次增加，不能跳
  2. pattern[k] != pattern[j]的时候前缀需要缩短，怎么缩短？k回溯一次
  3. 课本的这个版本next数组情况稍有不同，j位置的next值存的是以j-1为尾的后缀的长度，所以前缀指针匹配失败的时候，直接找next[k]就能找到k-1位置字符上一次出现的位置，回溯略微方便一点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int[] getNext(String pattern){
    int j = 0, k = -1;//双指针，同时k也表示当前的前后缀长度
    int next[] = new int[pattern.length()];
    next[0] = -1;
    while(j<pattern.length()-1){//构建的时候上一个位置的前后缀长度写在下一个位置的next上，所以只需要比较到倒数第二个，最后一个next也能写上
    if(k==-1 || pattern.chatAt(j)==pattern.charAt(k)){//k==-1表示是第一个，先加一下，如果两个指针的位置匹配成功也可以加一下
        j++;
        k++;//匹配成功那么前后缀长度加1
        next[j] = k;
    }
    else{
        //没有匹配成功，那么需要找上一个和k-1位置相同的字符，不对一下能不能和j位置匹配成功，那么上一个和k-1字符相同的在哪呢？在next[k]
        k = next[k];
    }
    return next;
    }
}

改进next数组
通过例子来看为什么需要改进

target a b c a b b a b c
pattern a b c a b c
next -1 0 0 0 1 2

那么从上述例子来看的话，由于target串中的b对比失败，需要将指针j回溯到j=2，但是很明显如果j=5没有匹配上的话，j=2也匹配不上，因为j=5和j=2两个位置的字符一样！

所以，next数组还能进行改进，使得时间复杂度进一步下降

pattern a b c a b c
前后缀长度k(第一版next) -1 0 0 0 1 2
改进后的next -1 0 0 -1 0 0

这里的-1怎么理解？
回溯到-1和0是不一样的，0还需要比较一下i和j=0两位置的字符，失败的那个位置没有可以用的子串信息，只能和第0号字符比较了，但是如果回溯到了-1，说明，第0号元素也不用比较了，这一次的匹配失败已经证明了和第0个肯定不相同，直接回溯到-1，就能在下一次循环中让两个指针+1，不用浪费一次比较

总结一下怎么个改进思想：回溯j的时候，我们回溯到的位置是可利用子串的后一个位置，但是如果这个位置和匹配失败的位置的字符一样的话，那其实一定匹配不上，可以利用旧next表回溯的位置的next值接着缩短前后缀，因为那个位置的next值是匹配不上的时候用的，如果我们提前知道匹配不上那其实也就可以提前用这个信息，一直循环缩短到和j位置不一样为止，这样和j位置不一样的话起码还有得比，不然回溯位置一样的话根本不用比

一句话，回溯一定要回溯到不一样的字符，要是回溯位置和原来一样，那一定匹配失败，还得回溯，不如我们在next数组里就把这一步工作做了，减少indexOf()函数里while的工作量

改进就是避免跳转之后相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int[] getNext(String pattern){
    int j=0, k=-1;
    int[] next = new int(pattern.lenght());
    while(j<pattern.length-1){
        if(k==-1 || pattern.charAt(j)==pattern.chatAt(k)){
            j++;
            k++;
            if(pattern.chatAt(j==pattern.charAt(k)))
                next[j] = next[k];//用k处的next值复制给j处(缩短前缀)
                //这里有个问题，那要改进版的next需要连续缩短两次或者更多呢呢？
            else
                next[j] = k;//一直到不相等的时候才能用指针赋值
        }
        else
            k = next[k];//前缀缩短
    }
    return next;
}

如果改进版的next需要连续缩短前缀两次或者更多呢呢？
如果需要连续缩短，那么中间那个位置的它当年也是想这么想的，所以它存的就是匹配失败时需要跳转的位置，见下方例子

pattern a b c a b d a b c a b c a a
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13
第一代next -1 0 0 0 1 2 0 1 2 3 4 5 3 4
改进版next -1 0 0 -1 0 2 -1 0 0 -1 0 5 -1 4

这个例子中，计算改进版next时，9号元素a如果匹配失败需要返回3，但是3号元素也是a，所以此时需要k = next[k]，next[k]是-1而不是0，所以连续缩短前缀并不需要循环，一次就能到位

可以看到改进版的next数组各个数字并不连续