KMP算法

KMP算法指的是字符串模式匹配算法,问题是:在主串T中找到第一次出现完整子串P时的起始位置。该算法是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的,以其名字首字母命名。
参考:https://www.cnblogs.com/dusf/p/kmp.html

暴力匹配法

主串的指针需要回溯,浪费了大量效率

KMP算法

基于部分匹配表,先给模式串建立一个部分匹配表的数组(即next数组),再按照部分匹配表来与主串进行匹配,主串也因此避免了指针的回溯
先要算出next数组,next数组只与模式串相关,与主串无关,

计算next数组

public static void Getnext (int next[], char[] pat) {
    // 这样算出来的next数组在经过+1运算后就是标准的next数组了
    int j = 0, k = -1;
    next[0] = -1;  // -1为标志位,方便+1运算为0
    while (j < pat.length - 1) {  // 最后一位不用算最长前后缀,所以减1
        if ((k == -1) || (pat[j] == (pat[k]))) {
            j++; k++;
            next[j] = k;
        }else {
            k = next[k];  // 做一次局部KMP回溯,不必再从头开始匹配
        }
    }
}

这里主要说一下k = next[k]这里的代码,这里的意思是pat[j] != pat[k],但是有pat[j-1] == pat[k-1]即前一位是相等的,因此通过一种在该局部做一次KMP的方法去找前一位的最长前后缀,再去匹配,这样可以避免从头开始匹配。

KMP代码

求出next数组后其实就很简单了:

public static int KMP (String target, String pat) {
    char[] t = target.toCharArray();  // 先转为数组
    char[] p = pat.toCharArray();
    int[] next = new int[p.length];
    Getnext(next,p);
    System.out.println(Arrays.toString(next));
    int i = 0,j = 0;  // 初始化匹配位,i为主串,j为模式串
    while (i < target.length() && j < pat.length()) {
        if (j == -1 || t[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if(j == p.length) {
        return (i - j);
    }else {
        return -1;
    }
}

优化

上述算法仍有缺陷,例子:
image.png
next数组应该是[-1,0,0,1],所以下一步匹配应该从1下标的B开始
image.png
这一步是无意义的,因为后一个的B不匹配,那前面的B也不会匹配,也就是说当p[3] != t[3]时,p[next[3]] != t[3]时肯定的,这里就没必要再匹配了,这个状态的后缀串和既然匹配不上,next数组获取的前缀串也必然匹配不上,知道了这个问题,怎么解决呢?这里需要修改一下next数组,不再记录完整的最长前后缀,而是当后缀与前缀完全匹配时,与主串不匹配就直接回溯到最前缀的next[j]上,
修改next数组代码:

public static void Getnext (int next[], char[] pat) {
    // 这里生成的next数组就不是标准的按最长前后缀来的了
    int j = 0, k = -1;
    next[0] = -1;  
    while (j < pat.length - 1) {  
        if ((k == -1) || (pat[j] == (pat[k]))) {
            if (pat[++j] == pat[++k]) {
	        next[j] = next[k];  // 直接回溯到最前的前缀
            }else {
                next[j] = k;
            }
        }else {
            k = next[k];  // 做一次局部KMP回溯,不必再从头开始匹配
        }
    }
}

完整代码

import java.util.Arrays;

public class myjava {
    public static void main(String[] args) {
        String pat = "aawaawaa";
        String target = "aawacaaaaaaawaaba";
        System.out.println(KMP(target,pat));
    }

    public static void Getnext (int next[], char[] pat) {
        int j = 0, k = -1;
        next[0] = -1;  // -1为标志位,方便+1运算为0
        while (j < pat.length - 1) {  // 最后一位不用算最长前后缀,所以减1
            if ((k == -1) || (pat[j] == (pat[k]))) {
                if (pat[++j] == pat[++k]) {
                    next[j] = next[k];
                }else {
                    next[j] = k;
                }
            }else {
                k = next[k];  // 做一次局部KMP回溯,不必再从头开始匹配
            }
        }
    }

    public static int KMP (String target, String pat) {
        char[] t = target.toCharArray();  // 先转为数组
        char[] p = pat.toCharArray();
        int[] next = new int[p.length];
        Getnext(next,p);
        System.out.println(Arrays.toString(next));
        int i = 0,j = 0;  // 初始化匹配位,i为主串,j为模式串
        while (i < target.length() && j < pat.length()) {
            if (j == -1 || t[i] == p[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if(j == p.length) {
            return (i - j);
        }else {
            return -1;
        }
    }
}

Q.E.D.


刚毕业走上社会被毒打的搬砖狗