KMP算法原理解析

B站看到“左神”有关KMP算法的详解，直接醍醐灌顶。

视频链接：算法讲解100【扩展】 KMP算法原理和代码详解

KMP算法详解：

• 1 理解Next数组的定义：前缀和后缀的最大匹配长度
  • 1.1 next[0] = -1, next[1] = 0
  • 1.2 位置i的前后缀最大匹配长度：
    • 不包含当前位置i的字
    • 不能整体
• 2 在Next数组的基础上，KMP算法如何进行匹配（两个核心理解）。
  • 2.1 s1字符串初始位置到next[i]下标内不可能匹配上（反证法）
  • 2.2 s1字符串next[i]下标位置到s2的i位置，利用了前缀和后缀最大匹配长度相等的原理
  • 2.3 故s1的i与s2的next[i]开始进行下一次匹配
• 3 Next数组如何快速生成（1个核心理解）
  • 3.1 s2数组中next[i]与s2[i-1]是否相等，相等则next[i]=next[i-1]+1;
• 4 KMP代码详解。

next数组的深层含义：

• 1 next[i]中的值，不仅为前缀和后缀的最大匹配长度，同时还是下一次匹配的s2数组的索引位置。

在Next数组的基础上，KMP算法如何进行匹配：

• 1 如果s1数组和s2数组匹配
  • s1[x]=s2[y], x++, y++
• 2 如果s1数组和s2数组不匹配
  • y > 0 , y = next[y] （next数组回溯）
  • y ==0, x++ (s1数组位置x匹配失败，从x+1开始匹配)

Next数组如何快速生成：

• 1 如果s2[next[i-1]] == s2[i-1]
  • next[i] = next[i-1]+1
• 2 如果s2[next[i-1]]  != s2[i-1]
  • next[i-1] > 0, next[i-1] = next[next[i-1]];
  • next[i-1] ==0, next[i] = 0;

KMP算法：

int kmp(string s1, string s2){
        int m = s1.size(), n = s2.size();
        vector next = getNext(s2);
        int x = 0, y = 0;
        while(x < m && y < n){ if (s1[x] == s2[y]) { x++; y++; }else if (y > 0) y = next[y];
            else x++;
        }
        return y == n ? x - y:-1;
    }

Next数组生成：

vector getNext(string s2){
        vector next(s2.size(), 0);
        int m = s2.size();
        next[0] = -1;
        next[1] = 0;
        int i = 2, cur_next = 0;
        while(i < m){ if (s2[i-1] == s2[cur_next]) next[i++] = ++cur_next; else if (cur_next > 0) cur_next = next[cur_next];
            else next[i++] = 0;
        }
        return next;
    }