KMP 匹配算法全解

朴素匹配算法及其问题

1. 子串处于位置 0，我们欣喜地发现前 4 个字符都相等，但是等我们比较到第 5 个字符的时候，遗憾发现这一位并不相等，匹配失败。

2. 子串移动到位置 1，首字符即不相等。

3. 子串移动到位置 2，首字符即不相等。

4. 子串移动到位置 3，首字符即不相等。

5. 子串移动到位置 4，发现重叠部分所有字符都相等，匹配成功！

• 比较过程中，主串的游标没必要往回走，比如过现在主串的前 4 位都已经跟子串比较过了，那就没必要再将这前面 4 位再去跟子串比较了。主串的游标只往右走，不往回走。

• 既然确定主串的游标只要往右移动就行了，剩下来要确认的就是子串的游标问题。我们可以看到，当子串已比较字符中没有重复字符时，我们直接将子串的头部移动到当前主串游标所在位置，又从子串的第一位开始比较；而当子串已比较字符的头尾存在重复的话，我们则没必要回到第一位，而是回到重复字符的下一位继续比较。这个子串游标应该回到第几位的问题，我们称之为回溯。研究清了回溯问题，KMP 算法也就自然出来了。

next 数组

• next[0]
a 前面没有字符，因而 next[0] = 0

• next[1]
b 前面只有一个字符 a，因而 next[1] = 0 。注意，咱们计算 next[i]，是根据第 i 位之前的字符来计算的，不包括第 i 位本身，即图中蓝色背景的部分。

• next[2]
b 前面有两个字符「ab」，没有相等的，因而 next[2] = 0

• next[3]
b 前面有 3 个字符「aba」，其中首部的 a 和尾部的 a 是相等的，因而 next[3] = 1

• next[4]
「abab」中，首部的 ab 和尾部的 ab 重合，因而 next[4] = 2

• next[5]
「ababa」中，首部的 aba 和尾部的 aba 重合，因而 next[5] = 3

• next[6]
「ababab」中，首部的 abab 和尾部的 abab 重合，因而 next[6] = 4

• next[7]
「abababe」首尾没有重合，因而 next[7] = 0

//------ 计算字符串的回溯下标数组 --------
// str: 要计算的字符串
// next：用于存储回溯下标的数组
//----------------------------------------
void  getNextArr(char * str, int *next) {

    int length = strlen(str);

    int index1 = 1; // 固定串的游标
    int index2 = 0; // 移动串的游标

    next[0] = 0;

    while (index1 < length) {
        if (index2 == 0 || str[index1] == str[index2]) {
            next[index1] = index2;
            ++index1;
            ++index2;
        } else {
            index2 = next[index2];
        }
    }
}

KMP 算法的实现

//----------------------------
// KMP 字符匹配算法
// author: huangqiang
// date: 2020-09-13
//----------------------------


#include<stdio.h>
#include<string.h>
#include<stdbool.h>

//------ 计算字符串的回溯下标数组 --------
// str: 要计算的字符串
// next：用于存储回溯下标的数组
//----------------------------------------
void  getNextArr(char * str, int *next) {

    int length = strlen(str);

    int index1 = 1; // 固定串的比较下标
    int index2 = 0; // 移动串的比较下标

    next[0] = 0;

    while (index1 < length) {
        if (index2 == 0 || str[index1] == str[index2]) {
            next[index1] = index2;
            ++index1;
            ++index2;
        } else {
            index2 = next[index2];
        }
    }
}

void main() {
    // 主串
    char *mainStr = "abaaabababebabf";
    int mainStrLen = strlen(mainStr);
    // 子串
    char *subStr = "abababe";
    int subStrLen = strlen(subStr);
    // 回溯下标数组
    int next[subStrLen];
    // 调用 getNextArr 方法计算回溯下标数组
    getNextArr(subStr, next);

		// matched 变量用于存储匹配结果
    bool matched = false;

    int mainIndex = 0, subIndex = 0;
    // 配对生成了，退出; 到主串尾了，退出。
    while(!matched && mainIndex < mainStrLen)
    {
        // 对当前字符进行匹配
        if (mainStr[mainIndex] == subStr[subIndex]) {
            // 子串游标到尾了，说明匹配成功了
            if (subIndex >= subStrLen-1) {
                matched = true;
            } else {
                subIndex++;
                mainIndex++;
            }
        } else {
            if(subIndex > 0) {
                // 字串回溯的时候，主串的游标保持不动
                subIndex = next[subIndex];
            }
            else {
                subIndex = 0;
                mainIndex++;
            }
        }
    }


    printf("主串: %s\n子串: %s\n", mainStr, subStr);
    if (matched) {
        printf("匹配成功，起始下标: %d\n", mainIndex-subStrLen+1);
    } else {
        printf("匹配失败\n");
    }
    return;
}

KMP 算法的改进

//------ 计算字符串的回溯下标数组 --------
// str: 要计算的字符串
// next：用于存储回溯下标的数组
//----------------------------------------
void  getNextArr(char * str, int *next) {

    int length = strlen(str);

    int index1 = 1; // 固定串的比较下标
    int index2 = 0; // 移动串的比较下标

    next[0] = 0;

    while (index1 < length) {
        if (index2 == 0 || str[index1] == str[index2] && str[next[index2] != str[index2]] ) {
            next[index1] = index2;
            ++index1;
            ++index2;
        } else {
            index2 = next[index2];
        }
    }
}