KMP算法 -- next解釋

Chinyu included in Algorithm

2021-07-13 151 words One minute views

Contents

KMP 基本概念

一種用來字符串匹配的算法一些定義：

s[] 為主字串， p[] 是匹配串，即可以理解成p是否是s的子字串
前綴：包含首位字符但不包含末位字符的子字串; 後綴：包含末位字符但不包含首位字符的子字串
部分匹配值：前綴與後綴最長共有長度
next[] 存的是每個下標對應的部分匹配值

核心思考：每次匹配失敗時，把p串往後移動至next對應的值

next的含義與模擬

字串從1開始存，next[i], 是p[1,i]中前綴和後綴相同的最大長度（部分匹配值），定義 next[1] = 0 例如：

1
2
3


idx  1 2 3 4 5 6
str  a b c a b a
next 0 0 0 1 2 1

求next陣列的code

1
2
3
4
5
6
7


// m 為 p 的長度
for(int i = 2, j = 0; i <= m; i++)
{
    while(j && p[i] != p[j + 1]) j = ne[j]; //已經有部分匹配值後，且匹配失敗，回退到上一個 
    if(p[i] == p[j + 1]) j++;
    ne[i] = j; // j為要回退的位置
}

匹配過程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


for(int i = 1, j = 0; i < n; i ++)
{
    while(j && s[i] != p[j + 1]) j = ne[j];
    if(s[i] == p[j + 1]) j++;
    if(j == m)
    {
        //匹配成功
        j = ne[j]; // 繼續匹配下一個字串
    }
}