KMP算法笔记

前言

最近一个月，坚持每天上Leetcode做一道算法题。这周每天推送的算法题，大部份都跟字符串有关且有两天的较困难的题目都用到了KMP算法，KMP算法步骤不算复杂，但也需要我花了点时间去理解，下面对我的理解进行记述。

主文

结合代码讲解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
String s = "babbbabbaba";
Integer len = s.length();
Integer fail[] = new Integer[len];
Arrays.fill(fail, -1);
Integer j = -1;
for (Integer i = 1;i < len;i++) {
    j = fail[i - 1];
    while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
        j = fail[j];
    }
    if (s.charAt(j + 1) == s.charAt(i)) {
        fail[i] = j + 1;
    }
}

对于字符串s，KMP的核心任务是先构建一个fail数组，fail数组成员fail[i]的值k表示s[0:k - 1] == s[i + 1 - k:i + 1](以i为末位的长度为k的子字符串等于s的k长前缀)。

上面12~13行比较好理解，由于上一次比较的结果是j = fail[i - 1]，那假如这次比较也相等，自然fail[i] = fail[i - 1] + 1 = j + 1