KMP算法

为方便 i,j 更清晰的移位,字符数组第一位丢掉不要,即序号从1开始

引子 – BF算法

主串S和模式串P匹配过程途中失败,则模式串指针 j = 1 (从头开始),主串指针需要回溯到 i = (i – j + 1) + 1 (本次匹配的初始位置 i0 + 1)。最坏的时间复杂度即为 (n – m) * m + m = (n – m + 1) * m = O(nm)

阿Q对KMP算法的理解

BF算法,每次都把 i 回溯,j 退为1(正常人都能想到)。但是在匹配过程中主串还需要要回溯嘛?如果回溯,之前匹配的信息是否没利用上了?

KMP算法好处就在于主串的指针是只增不减的,其当次匹配失败的位置的前K个字符(倒过来)如果和模式串的前K个字符是相同的,那本次匹配成功的就有K个字符,如下图:

由图可以看出下一次匹配启动时:主串的指针 i 不变,模式串逻辑上往后移动了 j – k (注意是逻辑上)。

那么关键在于哪呢?阿Q:在于模式串当前位置匹配失败后,下一次 j 应该去哪。【 next[j] ♥】

next[j]

注意:以下讨论的序号都是从 1 开始,若从零开始, next[j] = next[j] – 1

下面我们来个next[j]的题目,看图就理解了(做题人视角)

如果编写成程序呢?该怎么办?不可能说比 {aba}的前缀和后缀的交集吧(不服可以试试)

那接下来我们换种思路来考虑这个问题。(编程视角)

nextval(x)

编程任务(408统考不考KMP算法题)

阿Q备注:以下均用定长顺序存储实现 – SString(参考:串的存储

1、编写 KMP算法(获取模式串 next[j] 和 nextval[j])

// C实现
// 假设先通过代码实现了next[j]的计算
// 数组下标从1开始,0不管
int Index_KMP(SString S, SString P, int next[]){
    int i = 1, j = 1;
    while(i <= S.length && j <= P.length) // 不超过上限
    {
        if(S.ch[i] == P.ch[j] || j == 0) ++i, ++j;  // 阿Q备注:此时 j = 0 时,i也需要 + 1
        else j = next[j];
    }
    // P找完了
    if(j > P.length) return i - P.length;
    else return 0;
}

// 下面才是重头戏,编程实现next[j]的计算
void get_next(SString P, int next[]){
    next[1] = 0; // 规定
    int i = 1, j = 0;
    // 给 next 各项赋值
    while(i < P.length)
    {
        /*
            已知 next[j] 求 next[j + 1]
                p.ch[next[j]] == p.ch[j] -> next[j + 1] = next[j] + 1
                p.ch[next[j]] != p.ch[j] -> j = next[j] (递归) -> p.ch[k*] == p.ch[j]
                j == 0 -> next[j+1] = next[1] + 1;
        */
        if(j == 0 || P.ch[i] == P.ch[j]){
            ++i, ++j;
            next[i] = j; //阿Q备注: j在此处为 k* + 1,在循环外始终为 k*
            // 阿Q思考:经测试:next[i] = next[j] + 1 出错,问题在哪呢? 还是 j = k* + 1,不为 i -1
            // 经测速 next[i] = next[i - 1] + 1 也出错,问题在哪呢? 因为i只增,next[2] = next[1] + 1 = 2 错误
        }
        else j = next[j];
    }
}

// next的改进算法
void get_nextval(SString P, int nextval[]){
    int i = 1, j = 0;
    nextval[1] = 0; // nextval[1] = next[1]
    /*
        与next[j]不同点在于:
            还需进一步判断 p.ch[next[j]] ?= p.ch[next[next[j]]]
    */
    while(i < P.length){
        if(j == 0 || P.ch[i] == P.ch[j]){
            ++i, ++j;
            // 下面为不同点,需额外判断
            if(P.ch[i] == P.ch[j]) nextval[i] = nextval[j];
            else nextval[i] = j;
        }
        else j = nextval[j];
    }
}

// 经测试,代码正确

2、模式串在主串中有多少个完全匹配的字串

// C实现
int count_total_index_KMP(SString S, SString P, int next[], int index[])
{
    int i = 1, j = 1;
    int count = 0; // 记录完全匹配的个数
    // 下标从 1 ~ length
    while (i <= S.length){
        while(j <= P.length && i <= S.length){
            if(S.ch[i] == P.ch[j] | j == 0) ++i,++j;
            else j = next[j];
        }
        if(j > P.length){
            count += 1;
            // j 回溯到 1(从头比), i = i - P.length + 1
            index[count] = i - P.length;
            j = 1; 
            i = i - P.length + 1;
        }
    }
    return count;
}
// 阿Q:上述函数是重点,以下为测试
int main(){
    // 创建主串S和模式串P
    SString S, P;
    char *chs = "zaabaabbabaabaabbabaab"; // 第一位随意插值,下标从1开始
    int slen = 21;
    int i = 1;
    for(;i <= slen;i++) S.ch[i] = chs[i];
    S.length = slen;
    char *chp = "zabaa";
    int plen = 4;
    for(i = 1; i <= plen; i++) P.ch[i] = chp[i];
    P.length = 4;
    int next[5];
    get_next(P,next);
    //P在S中完全匹配
    //分段匹配即可,定一个数组记录各次匹配成功的位置。
    //int index[MAXINDEXLEN];
    /*
        范围: 1->a1 ; a1 + 1->a2; ...; an-1 + 1 -> an; an + 1->MAXINDEXLEN
    */
    // 需要临时创建一个SString temp 存放主串中未匹配的剩余字符串
    // 每段匹配成功的pos + 当前匹配开头的位置 ak + 1
    // 阿Q:上述当然可以,但最后能修改下 Index_KMP函数(更简洁)
    // Index_KMP 函数 修改为 count_total_index_KMP 函数

    int index[MAXINDEXLEN];
    int count = count_total_index_KMP(S,P,next,index);
    printf("%d\n", count);
    for(int i = 1; i <= count; i++)
        printf("%d ",index[i]);
    return 0;
}

/*
输出:
4
2 8 11 17 
*/

评论

发送评论 编辑评论


				
上一篇
下一篇