KMP + 拓展KMP[模闆]

KMP

字元串比對問題

得到失配指針，fail的值為上一次比對到的最長長度-1，因為是公共字首，是以也就是下标-1

得到上一次比對位置j後，目前位置與j+1位置 字母相同則比對長度+1，否則無法比對，即為-1

a	a	b	a	b	a	a	b
fail	-1	-1	-1	1	2

void getFail(char* ptr, int *fail){
    int m = strlen(ptr), j = -1;
    fail[0] = -1;
    for(int i=1; i<m; ++i){
        while(j!=-1 && ptr[i]!=ptr[j+1]) 
            j = fail[j];     
        fail[i] = ptr[i]==ptr[j+1]? ++j: -1;
    }
}
           

比對

類似fail數組的獲得過程，j為上一次比對到的位置，也就是目前ptr與str已比對長度

如果目前str的位置i與ptr的位置j的下一位比對，則長度+1,即 ++ j，長度滿足m-1，比對成功

void find(char* str, char* ptr, int* fail){
    int n = strlen(str), m = strlen(ptr);
    getFail(ptr, fail);
    int j = -1;
    for(int i=0; i<n; ++i){
        while(j!=-1 && str[i]!=ptr[j+1])
            j = fail[j];
        if(str[i] == ptr[j+1]) ++ j;
        if(j == m-1)
            printf("%d\n", i-m+2);
    }
}
           

拓展KMP

在O(|S| + |T|)的時間複雜度上，計算出文本串str的所有字尾與模式串ptr的最長公共字首，類似manacher

一篇優秀的文章：劉毅-拓展kmp

getNext:  next[ ] 為ptr的字尾與ptr的公共字首

getExtend：extend[ ] 為str的字尾與ptr的公共字首

i	1	2	3	4	5	6	7
S	a	a	a	a	a	b	b	b
T	a	a	a	a	a	c
extend[i]	5	4	3	2	1

獲得extend：不了解看劉毅裡面的圖

1. 如果

   i + next[i - a] < p

   ，此時

   extend[i] = next[i - a]

   。

2. i + next[i - a] == p，

   S[p]

   有可能等于

   T[p - i]

   ，是以我們可以直接從

   S[p]

   與

   T[p - i]

   開始往後比對，加快了速度。

3. i + next[i - a] > p，

   S[p] != T[p - i]

   ，是以就沒有繼續往下判斷的必要了，我們可以直接将

   extend[i] 

   =  

   p - i

   。

void getNext(char* ptr, int* next){
    int p = 0, st = 0;      //st為達到最遠位置p的起始點
    int m = strlen(ptr);
    next[0] = m;
    for(int i=1; i<m; ++i){
        if(i >= p || i + next[i-st] >= p){
            if(i >= p)
                p = i;      //超過即重新比對
            while(p < m && ptr[i] == ptr[p - i])
                ++ p;
            next[i] = p - i;
            st = i;
        }
        else 
            next[i] = next[i - st];
    }
}

void getExtend(char* str, char* ptr, int* next, int* extend){
    int n = strlen(str), m = strlen(ptr);
    getNext(ptr, next);
    
    int st = 0, p = 0;
    for(int i=0; i<n; ++i){
        if(i >= p || i + next[i-st] >= p){
            if(i >= p)
                p = i;
            while(i < n && p-i < m && str[i] == ptr[p - i])
                ++ p;
            extend[i] = p - i;
            st = i;
        }
        else 
            extend[i] = extend[i - st];
    }
}