前言

现在才想起大二算法课的良苦用心，秋招还得再捡起来。

KMP 一直是老大难问题，实际上就是一个 next 数组求法。

Next 数组

为什么要有这个东西？ 方便快速跳过相同前缀，不用匹配到一半发现不对又回去从头重新匹配。

所以 next 是指，匹配失败了，下一个找前面的谁。

比如下面两个字符串比较：

aafaabaafaab

aabaaf

求出 aabaaf 的 最大匹配前后缀数组：[0, 1, 0, 1, 2, 0]

全部 -1 得到 next 数组：[-1, 0, -1, -1, 1, -1]

涉及到一个求 next 数组的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int[] next(String s){
  int[] next = new int[s.length()];

  int j = -1;
  next[0] = j;

  for(int i = 1; i < next.length; i++){ // 0 已经设置好了
    while(j >= 0 && s.charAt(i) != s.charAt(j + 1)){
      // 不匹配，回退
      j = next[j];
      // 为什么不是 j--，这里相当于是在和自己匹配，有 next 就用
    }
    if(s.charAt(i) == s.charAt(j + 1)){
      // 匹配成功就向前一格
      j++;
    }
    // 因为 j++ 了，所以不用 j + 1
    next[i] = j;
  }

  return next;
}

匹配

思想继承了 next 数组，甚至连代码都差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int strStr(String haystack, String needle) {
  if(needle.length() == 0){
    return 0;
  }
  int[] next = next(needle);

  int j = -1;
  for(int i = 0; i < haystack.length(); i++){
    while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)){
      j = next[j];
    }
    if(haystack.charAt(i) == needle.charAt(j + 1)){
      j++;
    }
    // 这上面和 next 求法一样

    // 下面只需要判断是否匹配完成就行
    if(j == needle.length() - 1){
      return i - j;
    }
  }

  return -1;
}

拓展

重复的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:

输入: s = "aba"
输出: false
示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

next 数组还有更巧妙的用法：

比如 abcabcabcabc：

next = [-1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]

不用倒过来看，就是按照顺序排列的

可以看到 next 数组在初始字符串之后开始呈现规律递增

最终也是停留在了 next.length() - sub.length() - 1

不难发现，想要最后一个子串全匹配， sub.length() 就得把 next.length() 整除

因此，判断是否整除成为了检查条件。

1
2
3
4
5
6
7
8
9
public boolean repeatedSubstringPattern(String s) {
  int[] next = next(s);

  int rep = next.length - (next[next.length - 1] + 1);
  if(rep != next.length && next.length % rep == 0){
    return true;
  }
  return false;
}