好几年前在灯神的视频中第一次看懂的KMP，现在复习下

原理

使用公共前后缀，优化暴力匹配
（后缀已经比较过，前缀相同的话可以省略对比）

步骤

在原字符串 abaacababcac 中
匹配字符串 ababc

Step 1. 找到匹配字符串的所有前缀

前缀

Step 2. 找每个前缀对应的最长公共前后缀

最长公共前后缀

Step 3. 构建前缀表 prefixTable ，数组下标从0开始，去掉最后一个前缀，第一位加 -1 或 0

前缀表

Step 4. 使用前缀表匹配，每次可以少匹配曾匹配正确的公共前后缀

上一次错误匹配，正确匹配 a b a
省略 aba 的公共前后缀进行匹配
a 无真·公共前后缀则移动到-1

Step 5. 根据前缀规律进一步优化前缀表

前缀规律

Step 6. 使用前缀表匹配字符串，双指针，挨个匹配，错误则跳表，直到结束

代码

#include <stdio.h>
void prefix_table(char pattern[],int prefix[],int n){
  prefix[0] = 0
  int len = 0
  int i = 1
  while (i < n){
    if (pattern[i] = pattern[len]) {
      len ++
      prefix[I] = len
      I ++
    }  else{ // 不相等
      if (len > 0){
        len = prefix[len - 1];
      }else{
        prefix[i] = len;
        i ++;
      }
    }
  }
}

int main(){
  char pattern[] = "ABABCABAA";
  int prefix[9];
  int n = 9;

  prefix_table(pattern, prefix, n);

  int I;
  for (i = 0; i < n; i ++){
    printf("%d\n",prefix[I]);
  }
  return 0;
}

function prefix_table(patternString){
  let prefix = [0]
  let flag = 0
  for (let i = 1; i < patternString.length; i ++) {
    if (patternString[i] == patternString[flag]){
      flag ++
      prefix[i] = flag
    }else{
      if(flag > 0){
        flag = prefix[flag - 1]
      }
      prefix[i] = flag
    }
  }
  return prefix
}

const patternString = "ABABCABAA"
let prefix = prefix_table(patternString)

console.log('prefix:',prefix)

const allString = 'ABABABCABAABABABAB'
prefix = [-1,...prefix.slice(0,-1)]
console.log('start pattern:\nmove_prefix:',prefix)

let flag_S = 0, flag_s = 0

while(flag_S < allString.length){
  if(flag_s == patternString.length - 1 && allString[flag_S] == patternString[flag_s]){
    console.log('Found patter at',flag_S - flag_s)
    flag_s = prefix[flag_s]
  }
  if(allString[flag_S] == patternString[flag_s]){
    flag_S ++
    flag_s ++
  }else{
    flag_s = prefix[flag_s]
    if (flag_s == -1){
      flag_S ++
      flag_s ++
    }
  }
}

// 输出
prefix: [
  0, 0, 1, 2, 0,
  1, 2, 3, 1
]
start pattern:
move_prefix: [
  -1, 0, 0, 1, 2,
   0, 1, 2, 3
]
Found patter at 2

前缀表创建优化

前缀规律1
若前缀的最后一个字母==上一个前缀的最长公共后前缀的下一个字母
则 最长公共前后缀 = 上一个最长公共前后缀 + 最后一个字母
最长公共前后缀长度 = 上一个最长公共前后缀长度 + 1 前缀规律2

若前缀的最后一个字母==上一个前缀的最长公共前后缀的最后一个字母
!=上一个前缀的最长公共前缀的下一个字母
则 最长公共前后缀 = 上一个前缀的最长公共前后缀的最后一个字母 = 首字母 = 最后一个字母
最长公共前后缀长度 = 1

若 都不同则
最长公共前后缀长度 = 0