数据结构-KMP模式算法

最近很久没有看Java的知识了，都在看看数据结构，一连看了一周，数据结构理解不难，但是真正的算法理解还是比较困难的，所以开一个坑。接下来会继续更新其他算法，线性表貌似只涉及这一个算法233333
掘金：https://juejin.im/post/5cb0cf34e51d456e71408592

参考书籍《大话数据结构》

1. 算法原理

KMP模式算法，用来解决查找最小子串的问题，相对于暴力算法来说，避免了重复比较的过程。
图1-重复比较的示意图（图源《大话数据结构》）
从图中可以看到，我们可以知道②③④⑤⑥是没有必要的操作，因为我们已经遍历过了这些数据，为什么不能直接跳过他们呢？
我们分析我们的暴力求解方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//C语言实现，平均时间复杂度(n+m)/2
int getIndex(String s, String t, int pose){
    int i = pose;//母串下标值
    int j = 1;//表示当前子串的下标值,在这里string下标为0的数据为字符串的长度
    while (i <= s[0] && j<= t[0]) {//若i小于s长度且j小于t的长度的时候j循环,j>t[0]时表示有解
        if (s[i] == t[i]) {
            i++;
            j++;
        }else{
            i = i-j+2;//将母串的下标值回溯
            j = 1;
        }
    }
    if (j > t[0])//大于则表示有解
        return i - t[0];
    else
        return 0;
}

从上图可以看到，我们算法要实现的就是避免i的回溯，以节省掉一些不必要的判断，既然禁止了i的回溯，那么我们就看看j是如何变化的。
根据图1，我们可以发现，除去我们需要丢掉的，j从6变回了1，需要被查找的子串abcdex的首字母a和bcdex中的任何一个字符不同，然后我们来看下面这个例子。
图2-例子
我们发现，由于子串中的开头的ab和后面的第四个字符开始的ab相等，所以j变成了3。故我们得出规律：
j值的多少取决于当前字符之前的串的前后缀的相似度。
我们可以根据这个值给这个子串做一个特征数组(next数组)，数组长度和子串相等，专门用来描述这一特性。

1.1 next数组值推导

next数组有如下推导原则：

  • 当j = 1时 这个下标下的特征数组值为0
  • 当1~j-1的串中有两个字符相等的时候，值为相等的前缀字符最后一个字符的下标+1
  • 其他情况时，值为1

例子：

  • 子串为“abcdex”
    1) 当j = 1时，next[1] = 0;
    2) 当j = 2时，b的前面就一个字符，属于其他情况，next[2] = 1
    3) 当j = 3时，c的前缀字符是b，和前面没有相等的字符，所以属于其他情况，next[3] = 1；
    4) 以此类推，最终的next数组为：011111。

  • 子串为“abcabx”

  1. 当j = 1时，next[1] = 0；
  2. 当j = 2时，next[2] = 1;
  3. j = 3，4时同理，为1；
  4. 当j = 5时，b前面的字符串为”abca”，最后的a前面的首字符a相同，a的下标是1，所以next[5] = 1+1 = 2；
  5. 当j = 6时，x前面的字符串为”abcab”,后缀的ab和前缀的ab是相同的，b的下标是2，所以next[6] = 2+1 = 3；
  6. 所以最终的next数组为：011123
  • 子串为”ababaaaba”
  1. j = 1, next[1] = 0;
  2. j = 2, next[2] = 1;
  3. j = 3, next[3] = 1;
  4. j = 4, next[4] = 2;因为b前的字符串”aba”中前缀字符a和后缀字符a相等，1+1 = 2；
  5. j = 5, next[5] = 3;”abab” ab = ab 2+1 = 3;
  6. j = 6, next[6] = 4;”ababa”中，前缀字符串”aba”和后缀字符串”aba”相等，即使中间的a是共享的;
  7. j = 7, next[7] = 2;”ababaa”中，前缀字符a和后缀字符a相等，所以1+1 = 2；
  8. 以此类推，next：011234223；

接下来我们就要运用这个next数组来实现我们的KMP模式算法了

2. 算法实现

首先是获得next数组的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void get_next(string t, int *next){
    int i, j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i<next[0]) {//next[0]是next数组的长度
        if (j == 0 || t[i] == t[j] ) {
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

然后是使用这个next特征数组进行查找子串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Index_KMP(string s, string t, int pos){
    int i = pos;
    int j = 1;
    int next [255];
    get_next(t, next);//获得next数组
    while (i <= s[0] && j <= t[0]) {
        if (j==0 || s[i] == t[j]) {//对比暴力方法多加入了一个j的判断,减少了遍历次数
            i++;
            j++;
        }else{
            j = next[j];//对比暴力方法多加入了一个j回退到合适的位置,而不是直接退回到1,而i不变
        }
    }
    if (j > t[0])//有解
        return i=t[0];
    else
        return 0;//无解
}

KMP模式其实还有能够优化的地方，今晚到点熄灯了，下次再说

3. 总结

KMP模式算法对比暴力破解法，其实改变了回溯的机制，使得遍历的次数少了，从而做到了相对高效。但是这种算法只有在有子串中有很多干扰项的时候才能对比出优越性。