KMP

Published by powerflyang on Jul 13, 2022

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

KMP算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

前缀表（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 * needle: abcdabc
5 * next[0]: 0
6 * i = 1, j = 0, i->b j->a , next[1] = 0
7 * i = 2, j = 0, i->c j->a , next[2] = 0
8 * i = 3, j = 0, i->d j->a , next[3] = 0
9 * i = 4, j = 0, i->a j->a , next[4] = 1
10 * i = 5, j = 1, i->b j->b , next[5] = 2
11 * i = 6, j = 2, i->c j->c , next[6] = 3
12 * i = 7 break;
13 */
14export function getNext(needle: string) {
15  const next = [0];
16  let i = 1;
17  let j = 0;
18  while (i < needle.length) {
19    if (needle[i] === needle[j]) {
20      next[i] = j + 1;
21      i++;
22      j++;
23    } else if (j > 0) {
24      j = next[j - 1];
25    } else {
26      next[i] = 0;
27      i++;
28    }
29  }
30  return next;
31}

next 数组的应用

typescript
1export const ImplementStrStr = (haystack: string, needle: string): number => {
2  if (needle.length === 0) {
3    return 0;
4  }
5  const next = getNext(needle);
6  let j = 0;
7  for (let i = 0; i < haystack.length; i++) {
8    while (j > 0 && haystack[i] !== needle[j]) {
9      // ababbabababdabbac, abaaba next=[0,0,1,1,2,3]
10      // 0123456789
11      // i = 2, j = 2
12      // i = 3，j = 0
13      // i = 4，j = 0
14      // i = 5，j = 1
15      // i = 6，j = 2
16      // i = 7，j = 3 // next 数组的作用
17      // i = 8，j = 1 // 最大相同前后缀可以直接跳过 j=3, aba 最大相同前后缀长度为1。
18      // i = 9，j = 2
19      // i = 10，j = 1 // ...
20      j = next[j - 1];
21    }
22    if (haystack[i] === needle[j]) {
23      if (j === needle.length - 1) {
24        return i - j;
25      }
26      j++;
27    }
28  }
29  return -1;
30};