KMP

原文链接 多图预警👊🏻详解 KMP 算法

前缀表(next 数组)

next 数组存放的是当前长度下的 最长相同前后缀 的长度 以 abcabf 举例

  1. a 时,最长前后缀长度是 0

    因为是。总长度就只有 1 的话单独一个字母不算做

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

  2. ab 时,很显然长度也是 0

  3. abc 时,很显然长度也是 0

  4. abca 时, 最长相同前后缀长度就是 1 了,是 a

  5. abcab 时, 最长相同前后缀长度就是 2 了,是 ab

  6. abcabf 时,没有 最长相同前后缀了,长度是0

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

typescript
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
/**
 * 最大相同前后缀长度
 * 双指针
 * needle: abcdabc
 * next[0]: 0
 * i = 1, j = 0, i->b j->a , next[1] = 0
 * i = 2, j = 0, i->c j->a , next[2] = 0
 * i = 3, j = 0, i->d j->a , next[3] = 0
 * i = 4, j = 0, i->a j->a , next[4] = 1
 * i = 5, j = 1, i->b j->b , next[5] = 2
 * i = 6, j = 2, i->c j->c , next[6] = 3
 * i = 7 break;
 */
export function getNext(needle: string) {
  const next = [0];
  let i = 1;
  let j = 0;
  while (i < needle.length) {
    if (needle[i] === needle[j]) {
      next[i] = j + 1;
      i++;
      j++;
    } else if (j > 0) {
      j = next[j - 1];
    } else {
      next[i] = 0;
      i++;
    }
  }
  return next;
}

next 数组的应用

typescript
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
export const ImplementStrStr = (haystack: string, needle: string): number => {
  if (needle.length === 0) {
    return 0;
  }
  const next = getNext(needle);
  let j = 0;
  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) {
      // ababbabababdabbac, abaaba next=[0,0,1,1,2,3]
      // 0123456789
      // i = 2, j = 2
      // i = 3,j = 0
      // i = 4,j = 0
      // i = 5,j = 1
      // i = 6,j = 2
      // i = 7,j = 3 // next 数组的作用
      // i = 8,j = 1 // 最大相同前后缀可以直接跳过 j=3, aba 最大相同前后缀长度为1。
      // i = 9,j = 2
      // i = 10,j = 1 // ...
      j = next[j - 1];
    }
    if (haystack[i] === needle[j]) {
      if (j === needle.length - 1) {
        return i - j;
      }
      j++;
    }
  }
  return -1;
};