串的模式匹配算法：BF算法与KMP算法

程序员文章站 2022-05-12 22:50:45

...

下面两种算法都是根据如果具体例子讨论
主串MainString: acabaabcabcacaabc
模式串ModelString: abaabca

1、BF算法

1）思路

分别用i,j记录主串MainString和模式串ModelString中当前正在比较的字符位置。i 初始值为0，j初始值也为0
当两个串均未到达串尾时：
1. 若MainString[i] == ModelString[j],则++i;++j
2. 若MainString[i] != ModelString[j],则主串回到最初匹配的后一位——i = i - j + 1; 模式串回到起点——j = 0。
结束的标志：i或者j达到相应串末尾。若j>=模式串ModelString的长度，则表明匹配完成。返回第一个匹配的头部位置：i - j + 1; 若j < 模式串ModelString的长度，则不存在匹配结果，返回0。

2）代码：

int BF(char* MainString, char* ModelString) {
    int LengthMain = strlen(MainString);
    int LengthModle = strlen(ModelString);
    if (LengthModle > LengthMain | LengthModle <= 0 | LengthMain <= 0) {    //不正常的情况直接退出
        printf("please input correct string\n");
        return -1;
    }

    int i = 0, j = 0;
    while (i < LengthMain&&j < LengthModle) {
        if (MainString[i] == ModelString[j]) {  //匹配，主串和模式串都向前进一
            i++; j++;
        }
        else {  //不匹配，模式串从第一个字母开始，主串回到最初的字母的后一位
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= LengthModle)                       //输入第一个匹配的位置，由于下标从0开始，所以加上1
        return i - LengthModle + 1;
    else
        return 0;                               //没有匹配，则输出0
}

2、KMP算法

1）优化BF的过程

在每次匹配过程中出现字符比较不相等时，不需要将i回溯(主串的标志)，j也不必直接回溯到0，而是根据已经匹配的信息，尽可能将j向右滑动，然后再继续比较。例如BF中第二次匹配知道MainString[1] = ‘c‘,ModelString[0] = ‘a‘,这一次就没必要进行比较。

那么如何找出已经匹配过的规律呢。为了方便说明，这里数组下标均从1开始，代码实现时再说明下标从0开始的区别。我们假设MainString[i] != ModelString[j] 时，j需要回溯到k(k<j).根据以上信息可以得出两个已知条件：

MainString[i-j+1, i-j+2, …….., i-1] = ModelString[1, 2,……, j-1]，这里我们为了方便与2.相结合，取其中的一部分：MainString[i-k+1, i-k+2, …….., i-1] = ModelString[j-k+1, j-k+2,……, j-1]——-(1)
MainString[i-k+1, i-k+2, …….., i-1] = ModelString[1, 2,……, k-1]——(2)
将(1)与(2)结合得：
ModelString[j-k+1, j-k+2,……, j-1] = ModelString[1, 2,……, k-1]，翻译成书面语言就是：当ModelString[j]与MainString[i]不匹配时，回溯点k与j直接存在一定的关系，从模式串ModelString第0位向右数k-1个数与从模式串ModelString第j-1位向左数k-1个数完全匹配(两者方向都是从左到右)

因此回溯值只与模式串有关，与主串无关。可以根据模式串先求出每一个位置对用的回溯值。用Next[j]来存储所有回溯值。则给出Next[j]的定义：

哇，这个markdown不能表示分段函数，很蠢。只能献上我的丑字了。
串的模式匹配算法：BF算法与KMP算法
由此可以得出模式串的Next数组：

但是这样的描述不适合计算机的计算，我们还应该再总结一下，使得Next[]方便计算机计算。

我们可以看出Next[]的出过程，相当于模式串ModelString中的子串与自己子串匹配。我们从关系式ModelString[ j-k+1, j-k+2,……, j-1 ] = ModelString[ 1, 2,……, k-1 ](即 Next[ j ] = k)出发，求Next[ j+1 ]：

当ModelString[ j ] = ModelString[ k ]时，则ModelString[ j-k+1, j-k+2,……, j-1, j ] = ModelString[ 1, 2,……, k-1, k ]。易知，Next[ j + 1 ] = k +1;
当ModelString[ j ] != ModelString[ k ]时，此时可以把求Next[]看成是一个模式匹配问题，其中模式串为ModelString,主串也为ModelString,因为ModelString[1] = ModelString[j-k+1]; ModelString[2] = ModelString[j-k+2]; ………; ModelString[k-1] = ModelString[j-1]; 而ModelString[k] != ModelString[j],这时模式串ModelString中标位k要尽量向右移，而不是回溯到0(BF算法)，根据以前的定义，回溯的标位为Next[k],记做k^’(k^’ = Next[k])。

(1). 若此时满足了，ModelString[k^’] = ModelString[j],则根据1.可知，Next[j+1] = k^’ + 1 = Next[k] + 1
(2).若此时ModelString[k^’] ！= ModelString[j]，则模式串还要进一步回溯。根据2.这一次回溯点k^‘’ = Next[k^’]…..找到满足的点ModelString[k*] = ModelString[j]然后转到(1)。否则一直回溯到k* = 1，转到(3)
(3).根据定义回溯到k* = 1代表不存在任何k*满足条件，因此，此时要将子串的第一位与主串j相比较，即Next[j+1] = 1.(这里说的第一位即下标为0的位置)

2）Next代码

void GetNext(char* ModelString, int *Next) {
    int LengthModle = strlen(ModelString);
    Next[0] = 0;
    int j = 0, k = 0;               //k = Next[j]
    while(j < LengthModle - 1){
        if (k == 0 || ModelString[j] == ModelString[k - 1]) {
            ++j; ++k; Next[j] = k;
        }
        else
            k = Next[k-1];
    }
}

代码写出来跟上述公式不一样，原因是公式中为了方便描述，数组下标都是从1开始，而程序中数组下标均从0开始。对应着ModelString[j]指向的是正确的字符，但是j的数值少1，所以k的数值也要减一。所以
判断条件ModelString[ j ] != ModelString[ k ] ===》 ModelString[ j ] != ModelString[ k-1 ]
1.中Next[j+1] = k + 1 ===》 Next[j] = k。
2.中k = Next[k] ===> k = Next[k-1]

3）主串MainString与模式串ModleString匹配

当MainString[i] == ModelString[j]时，双方都向右移一位，++i，++j
当MainString[i] ！= ModelString[j]，模式串需要回溯。j = Next[j-1],如果j回溯到0，转3
j = 0，说明ModelString[0] != MainString[i],下一步需要将ModelString[0]与MainString[i+1]比较。只需要执行++i即可
当i , j 超过对应串的串长时，算法终止。若j>=模式串ModelString的长度，则表明匹配完成。返回第一个匹配的头部位置：i - j + 1; 若j < 模式串ModelString的长度，则不存在匹配结果，返回0。

4）KMP代码

int KMP(char* MainString, char* ModelString) {
    int LengthMain = strlen(MainString);
    int LengthModle = strlen(ModelString);
    if (LengthModle > LengthMain | LengthModle <= 0 | LengthMain <= 0) {
        printf("please input correct string\n");
        return -1;
    }

    int *Next = (int *)malloc(LengthModle * sizeof(int));
    GetNext(ModelString,Next);

    int i = 0, j = 0;
    while (i < LengthMain&&j < LengthModle) {
        if (MainString[i] == ModelString[j]) {
             ++i; ++j;
        }
        else {
            if (j != 0) {
                j = Next[j - 1];
            }
            else {
                ++i;
            }
        }
    }
    if (j >= LengthModle)
        return i - LengthModle + 1;
    else return 0;
}

3、例子

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

int BF(char* MainString, char* ModelString);
int KMP(char* MainString, char* ModelString);
void  GetNext(char* ModelString, int *Next);

int main() {

    char* MainString = "acabaabcabcacaabc";
    char* ModelString = "abaabca";
    printf("The result of BF : %d\n",BF(MainString, ModelString));
    printf("The result of KMP : %d\n", KMP(MainString, ModelString));


    //printf("%s", MainString);
    //printf("%d", strlen(s));
    return 0;
}

int BF(char* MainString, char* ModelString) {
    int LengthMain = strlen(MainString);
    int LengthModle = strlen(ModelString);
    if (LengthModle > LengthMain | LengthModle <= 0 | LengthMain <= 0) {    //不正常的情况直接退出
        printf("please input correct string\n");
        return -1;
    }

    int i = 0, j = 0;
    while (i < LengthMain&&j < LengthModle) {
        if (MainString[i] == ModelString[j]) {  //匹配，主串和模式串都向前进一
            i++; j++;
        }
        else {  //不匹配，模式串从第一个字母开始，主串回到最初的字母的后一位
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= LengthModle)                       //输入第一个匹配的位置，由于下标从0开始，所以加上1
        return i - LengthModle + 1;
    else
        return 0;                               //没有匹配，则输出0
}

int KMP(char* MainString, char* ModelString) {
    int LengthMain = strlen(MainString);
    int LengthModle = strlen(ModelString);
    if (LengthModle > LengthMain | LengthModle <= 0 | LengthMain <= 0) {
        printf("please input correct string\n");
        return -1;
    }

    int *Next = (int *)malloc(LengthModle * sizeof(int));
    GetNext(ModelString,Next);

    int i = 0, j = 0;
    while (i < LengthMain&&j < LengthModle) {
        if (MainString[i] == ModelString[j]) {
             ++i; ++j;
        }
        else {
            if (j != 0) {
                j = Next[j - 1];
            }
            else {
                ++i;
            }
        }
    }
    if (j >= LengthModle)
        return i - LengthModle + 1;
    else return 0;
}

void GetNext(char* ModelString, int *Next) {
    int LengthModle = strlen(ModelString);
    Next[0] = 0;
    int j = 0, k = 0;               //k = Next[j]
    while(j < LengthModle - 1){
        if (k == 0 || ModelString[j] == ModelString[k - 1]) {
            ++j; ++k; Next[j] = k;
        }
        else
            k = Next[k-1];
    }
}

串的模式匹配算法：BF算法与KMP算法

串的模式匹配算法：BF算法与KMP算法

1、BF算法

1）思路

2）代码：

2、KMP算法

1）优化BF的过程

2）Next代码

3）主串MainString与模式串ModleString匹配

4）KMP代码

3、例子

Python字符串匹配算法KMP实例

Python实现字符串匹配的KMP算法

php中最简单的字符串匹配算法

python通过BF算法实现关键词匹配的方法

PHP实现的字符串匹配算法示例【sunday算法】

10、数据结果与算法 - 字符串匹配问题 KMP算法

串的模式匹配算法

串的模式匹配算法理论与思想

串的模式匹配算法理论与思想

串的模式匹配算法