文章目录
  1. 1. BF算法
    1. 1.1. 实例
    2. 1.2. 代码实现
  2. 2. KMP算法
    1. 2.1. 代码实现
    2. 2.2. 递推
    3. 2.3. 直接法

kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。在介绍KMP算法之前,我们先介绍一下BF算法。

BF算法

BF(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。

该算法最坏情况下要进行M(N-M+1)次比较,时间复杂度为O(MN)。

实例

S:  ababcababa

T:  ababa

代码实现

private int bfMatch(String s, String t) {
    int i = 0;
    int j;
    while (i < s.length()) {
        j = 0;
        while (j < t.length() && s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
        }

        if (j == t.length()) {
            return i-t.length();
        }

        i = i-j+1;
    }
    return -1;
}

其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=t0t1t2t3,又因为t0!=t1!,所以第六趟的匹配是多余的。又由于t0==t2,t1==t3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

KMP算法

KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示T[0…j-1]中最长后缀的长度等于相同字符序列的前缀。

对于next[]数组的定义如下:

  1. next[j] = -1 j = 0
  2. next[j] = max(k): 0<k<j T[0…k-1]=T[j-k,j-1]
  3. next[j] = 0 其他

即next[j]=k>0时,表示T[0…k-1]=T[j-k,j-1]

因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。

代码实现

private int kmpMatch(String s, String t) {
    int[] next = new int[t.length() + 1];
    int i=0;
    int j=0;

    next(t, next);

    while (i < s.length()) {
        if (j < t.length() && s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];
        }

        if (j == t.length()) {
            return i-t.length();
        }
    }

    return -1;
}

因此KMP算法的关键在于求算next[]数组的值,即求算模式串每个位置处的最长后缀与前缀相同的长度, 而求算next[]数组的值有两种思路,第一种思路是用递推的思想去求算,还有一种就是直接去求解。

递推

根据定义next[0]=-1,假设next[j]=k, 即T[0…k-1]==T[j-k,j-1]

  1. 若T[j]==T[k],则有T[0..k]==T[j-k,j],很显然,next[j+1]=next[j]+1=k+1;
  2. 若T[j]!=T[k],则可以把其看做模式匹配的问题,即匹配失败的时候,k值如何移动,显然k=next[k]。
private void next(String t, int[] next) {
    next[0] = -1;
    int k=-1,i=0;
    while (i<t.length()-1){
        if (k==-1 || t.charAt(i) == t.charAt(k) ) {
            i++;
            k++;
            next[i] = k;
        } else {
            k = next[k];
        }
    }
}

直接法

private void next(String t, int[] next) {
    for (int i=0; i<t.length(); i++) {
        if (i == 0) {
            next[i] = -1;
        } else if (i == 1) {
            next[i] = 0;
        } else {
            int j = i-1;
            for (; j>0; j--) {
                if (equals(t, i, j)) {      //找到最大的j值
                    next[i] = j;
                    break;
                }
            }

            if (j==0) {
                next[0] = 0;
            }
        }
    }
}

private boolean equals(String t, int i, int j) {  //判断t[0...j-1]与t[i-j...i-1]是否相等
    for (int m = 0,n=j+1; m<j&&n<i; m++,n++) {
        if (t.charAt(m) != t.charAt(n)) {
            return false;
        }
    }

    return true;
}
文章目录
  1. 1. BF算法
    1. 1.1. 实例
    2. 1.2. 代码实现
  2. 2. KMP算法
    1. 2.1. 代码实现
    2. 2.2. 递推
    3. 2.3. 直接法