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];
    }
}