KMP演算法詳解

2021 年 4 月 30 日
筆記
KMP, 演算法, 詳解

字元串專題

樸素模式匹配演算法

int Index (SSTring S, SString T) {
    int k = 1;
    int i = k;
    int j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++;
            j++;	//字元匹配成功，繼續比較後繼字元
        } else {
            k++;	//匹配不成功，主串S指針回退 
            i = k;
            j = 1;
        }
    }
    if (j > T.length) {
        return k;
    } else {
        return 0;	//這種情況是主串已經判斷完，但是要匹配的串還未完，所以匹配失敗
    }
}

KMP演算法

一、基礎知識

串的前綴：包含第一個字元，且不包含最後一個字元的子串

串的後綴：包含最後一個字元，且不包含第一個字元的子串

當第j個字元匹配失敗，由前1 ~ j – 1個字元組成的串記為S，則：next[j] = S的最長相等前後綴長度+1

特別的, next[1] = 0

例如：模式串：’ababaa’

序號j = 1的時候，S = ‘a’
序號j = 2的時候，S = ‘a’此時沒有前綴和後綴所以最長相等前後綴長度為0 + 1
序號j = 3的時候，S = ‘ab’ 此時前綴和後綴最長相等長度為 0 + 1
序號j = 4的時候，S = ‘aba’ 前綴 = ‘a’ 後綴 = ‘a’ 2 + 1
序號j = 5的時候，S = ‘abab’ 前綴 = ‘ab’ 後綴 = ‘ab’ 2 + 1
序號j = 6的時候，S = ‘ababa’ 前綴 = ‘aba’ 後綴 = ‘aba’ 3 + 1

序號j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

求模式串T的next數組

void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
   	while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            //若pi = pj , 則next[j + 1] = next[j] + 1
            next[i] = j;
        } else {
            //否則令j = next[j], 循環結束
            j = next[j];
        }
    }
    
    
}

求next數組的程式碼詳細解釋：

圖解：

加入此時k + 1 = 17

已知next[16]的值，所以可以知道下圖圈起來的部分重合

然後根據流程2，要求的是next[k + 1]，假如此時P₈ = P₁₆成立

假如P₈ = P₁₆ 也就是說下圖部分重合，所以next[k + 1] = 8 + 1 = 9
假如P₈ != P₆

3、如果next[8] = 4，則有以下關係

4、現在再判斷，如果P₁₆ = P₄則next[17] = 4 + 1 = 5

藍色重合

然後比較p₂是否等於p₁₆

KPM演算法

int Index_KMP (SString S, SString T) {
    int i = 1;
    int j = 1;
    int next[T.length + 1];
    get_next(T, next);	//求模式串的next數組
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;		//繼續比較後繼字元
        } else {
        	j = next[j];	//模式串右移
        }
        
    }
    
    if (j > T.length) {
        return i - T.length;	//匹配成功
    } else {
        return 0;
    }
}

總結

樸素模式匹配演算法的缺點：當某些子串與模式串能部分匹配時，主串的掃描指針i經常回溯，導致時間開銷增加。最壞時間複雜度O(nm)

KMP演算法：當子串和模式串不匹配時，主串指針i不回溯，模式串指針j = next[j],演算法平均時間複雜度：O(n + m)

next數組手算方法：當第j個字元匹配失敗，由前1 ~ j - 1個字元組成的串記為S，則：next[j] = S的最長相等前後綴長度 + 1
特別地，next[1] = 0

KMP演算法存在的問題(next數組的優化問題)

如上圖，I與g不匹配，所以指針j會指向next[j]的位置，也就是j會指向1的位置，此時字母為g

觀察可知，第一個字母與第一次j指向的字母相同，所以這就相當於多進行的沒必要的比較。

這個時候就需要進行next數組的優化

也就是讓4的next的值，變為next[4] = next[next[4]]

優化程式碼實現

先求出next數組
先令nextval[1] = 0
for (int j = 2; j <= T.length; j++) {
    if (T.ch[next[j]] == T.ch[j]) {
        nextval[j] = nextval[next[j]];
    } else {
        nextval[j] = next[j];
    }
}

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

d4d59d818c23770f6bce192a1a9c3240

Tags: KMP 演算法詳解