好幾年前在燈神的視頻中第一次看懂的KMP阱当，現(xiàn)在復(fù)習(xí)下
原理
使用公共前后綴，優(yōu)化暴力匹配
（后綴已經(jīng)比較過(guò)芹关，前綴相同的話可以省略對(duì)比）
步驟
在原字符串 abaacababcac 中
匹配字符串 ababc
Step 1. 找到匹配字符串的所有前綴
前綴
Step 2. 找每個(gè)前綴對(duì)應(yīng)的最長(zhǎng)公共前后綴
最長(zhǎng)公共前后綴
Step 3. 構(gòu)建前綴表 prefixTable 般此，數(shù)組下標(biāo)從0開始盖文，去掉最后一個(gè)前綴砍濒，第一位加 -1 或 0
前綴表
Step 4. 使用前綴表匹配，每次可以少匹配曾匹配正確的公共前后綴
上一次錯(cuò)誤匹配叫潦，正確匹配 a b a
省略 aba 的公共前后綴進(jìn)行匹配
a 無(wú)真·公共前后綴則移動(dòng)到-1
Step 5. 根據(jù)前綴規(guī)律進(jìn)一步優(yōu)化前綴表
前綴規(guī)律
Step 6. 使用前綴表匹配字符串蝇完，雙指針，挨個(gè)匹配，錯(cuò)誤則跳表短蜕，直到結(jié)束
代碼
#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
前綴表創(chuàng)建優(yōu)化
前綴規(guī)律1
若
前綴的最后一個(gè)字母==上一個(gè)前綴的最長(zhǎng)公共后前綴的下一個(gè)字母則 最長(zhǎng)公共前后綴 = 上一個(gè)最長(zhǎng)公共前后綴 + 最后一個(gè)字母
最長(zhǎng)公共前后綴長(zhǎng)度 = 上一個(gè)最長(zhǎng)公共前后綴長(zhǎng)度 + 1
前綴規(guī)律2
若前綴的最后一個(gè)字母==上一個(gè)前綴的最長(zhǎng)公共前后綴的最后一個(gè)字母
!=上一個(gè)前綴的最長(zhǎng)公共前綴的下一個(gè)字母
則 最長(zhǎng)公共前后綴 = 上一個(gè)前綴的最長(zhǎng)公共前后綴的最后一個(gè)字母 = 首字母 = 最后一個(gè)字母
最長(zhǎng)公共前后綴長(zhǎng)度 = 1
若 都不同則
最長(zhǎng)公共前后綴長(zhǎng)度 = 0
