Leetcode 28. Find the Index of the First Occurrence in a String

KMP 主要用在 pattern 匹配上。

比如给出一个字符串 s 和一个字符串 pattern ，请找出 pattern 第一次在 s 中出现的下标。

最长公共前后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

比如字符串 aaabcaaa 的最长公共前后缀是 aaa ，最长公共前后缀长度就是 3 。

前缀表

next[i] 表示 s[0...i] 这个子字符串的最长公共前后缀长度。

E.g.

1
2

s:      a a b a a f
next:   0 1 0 1 2 0

基本思路

j 代表 pattern 的前缀结尾，i 代表 s 的后缀结尾。

我们假设 pattern[0...j] 和 s[i-j-1...i] 是相等的，而 pattern[0...j+1] 和 s[i-j-1...i+1] 不想等，即末尾的 pattern[j+1] 和 s[i+1] 不想等。

为了方便起见，我们作如下命名：

  • pattern[0...j] 为 p1
  • pattern[0...j+1] 为 p2
  • s[i-j-1...i] 为 s1
  • s[i-j-1...i+1] 为 s2
  • pattern[j+1] 为char_p
  • s[i+1] 为 char_s

那么显然有以下结论：

  • length(p1) == length(s1)
  • length(p2) == length(s2)
  • p1 == s1
  • p2 != s2
  • char_p != char_s

由于 char_p 和 char_s 不想等，因此我们需要将 j 回退到之前的某个位置重新开始匹配。

回退到哪里呢？暴力匹配算法是直接将 j 回退到 0 ，然而当 p1 的某个前缀 p1_prefix 和 s1 的某个后缀 s1_postfix 相同时，即 p1_prefix == s1_postfix 时，我们其实就可以跳过这段字符串，直接将 j 放到 p1_prefix 的末尾，然后继续尝试匹配。

那么现在的问题就是怎么找这个 p1_prefix ？

由于 p1 == s1 ，因此 s1_postfix 其实就是相同长度的 p1 的后缀 p1_postfix ，也就是说我们之前的假设就可以重新写为 p1_prefix == p1_postfix 。

看到了吗，其实这就是在找 p1 的最长公共前后缀。

我们找到最长公共前后缀之后，把 j 挪到 p1_prefix 的末尾就行了。

如果我们构造出了一个 pattern 的前缀表 next ，那么假设现在 j 指向的是 char_p ，把 j 往前挪的代码就可以写为

1

j = next[j - 1];

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

class Solution {
 public:
  // 构造字符串 s 的前缀表
  // 在 getNext() 函数中，我们假设 s.length() >= 2
  void getNext(int* next, const string& s) {
    // j 有两重含义：
    // 1. 前缀的末尾下标
    // 2. 最长相同前后缀的长度
    // i 的含义是后缀的末尾下标
    // 初始化 j 为 0
    int j{0};
    // next[0] 很显然一定是为 0 的
    next[0] = 0;
    // 开始迭代
    // 我们的目标是在每次迭代的过程中，找到最长相同前后缀
    // s[0...j] == s[?...i]
    // i 从 1 开始迭代，因为 length >= 2 ，我们没必要讨论
    // i == 0 的情况
    int len = s.size();
    for (int i{1}; i < len; ++i) {
      // 当 s[j] 和 s[i] 不想等时，即前后缀不匹配的时候
      // 前缀末尾的下标 j 需要进行回退
      // a a a f a a a f
      //             j i
      // 回退到什么位置呢？
      // 注意观察，s[j] 和 s[i] 虽然不想等，但是前面这一段
      // aaafaaa 有着公共前后缀 aaa ，所以我们可以试着跳到
      // 前缀 aaa 的后面那个元素的位置 f，然后比较前缀 aaaf
      // 和后缀 aaaf 是否相同。
      // a a a f a a a f
      //             j i
      //       j       i
      // 由于前缀和后缀都有着公共的 aaa ，所以我们只需要比较
      // s[j] 和 s[i] 是否相同就行了。
      // 如果不相同，继续回退，直到 j 回退到起始位置 0。
      // 怎么把 j 跳到 f 的位置呢？f 在 aaa 的后面，aaa 是
      // aaafaaa 的最长公共前缀，所以 f 的下标就是 next[j - 1]
      while (j > 0 && s[i] != s[j]) {
        j = next[j - 1];
      }
      // 接下来处理当 s[j] == s[i] 的情况
      // 这种情况很简单，就是公共前后缀的长度增加了 1
      // 而由于 for 语句中的 ++i 使得后缀末尾 i 已经自增了 1
      // 我们只需要再让前缀末尾 j 自增 1 即可
      if (s[i] == s[j]) {
        ++j;
      }
      // 两种情况都处理完了，接下来更新 next[i]
      // 由于我们之前让 j 自增了 1，所以其实现在的情况是
      // 前缀 [0, j - 1] 和 后缀 [?, i] 相同
      // 然而 next[i] 是指最长公共前后缀的长度，因此长度可以用
      // j 来描述。
      next[i] = j;
    }
  }

  int strStr(string haystack, string needle) {
    int haystackLen = haystack.size();
    int needleLen = needle.size();
    if (needleLen == 0) {
      return 0;
    }
    // 开始创建 needle 的前缀表
    int next[needleLen];
    getNext(next, needle);
    // j 用来索引 needle ，它有两层含义
    // 1. 前缀的末尾下标
    // 2. 最长相同前后缀的长度
    int j = 0;
    // 开始迭代
    // 接下来的操作和 getNext() 中的迭代非常相似
    // 不过注意，现在 i 从 0 开始迭代，之所以不像 getNext()
    // 中那样从 1 开始迭代是因为 getNext() 不需要考虑 i == 0
    for (int i{0}; i < haystackLen; ++i) {
      // 首先讨论末尾不匹配的情况，我们需要回退 j
      while (j > 0 && needle[j] != haystack[i]) {
        j = next[j - 1];
      }
      // 接下来处理末尾相同的情况，那好说，直接往前推
      if (needle[j] == haystack[i]) {
        ++j;
      }
      // 成功找到匹配字符串，返回
      if (j == needleLen) {
        return i - needleLen + 1;
      }
    }
    return -1;
  }
};