BF算法 KMP算法（普通、快速模式匹配算法）及C语言

判断两个串之间是否存在主串与子串的关系，这个过程称为串的模式匹配。

• 在串的模式匹配过程，子串 T 通常被叫做“模式串”。

普通的模式匹配（“BF”算法）

判断两个串是否存在子串与主串的关系，最直接的算法就是拿着模式串，去和主串从头到尾一一比对，这就是“BF”算法的实现思想。

将提供的模式串（例如 “abcac” ）从主串的第一个字符开始，依次判断相同位置的字符是否相等，如果全部相等，则匹配成功；反之，将子串向后移动一个字符的位置，继续与主串中对应的字符匹配。

算法运行过程：（图中，i 和 j 表示匹配字符在数组中的位置下标）

如图所示，第一次匹配，模式串和主串匹配到第三个字符时，匹配失败；模式串向右移动一个字符的位置，还是从第一个字符 ‘a’ 和主串的第二个字符 ‘b’ 相匹配，匹配失败；模式串继续后移一个字符的位置，继续匹配。

#include <stdio.h>
#include <string.h>
int sel(char * S,char *T){
    int i=0,j=0;
    while (i<strlen(S) && j<strlen(T)) {
        if (S[i]==T[j]) {
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    //跳出循环有两种可能，i=strlen(S)说明已经遍历完主串；j=strlen(T),说明模式串遍历完成，在主串中成功匹配
    if (j==strlen(T)) {
        return i-strlen(T)+1;
    }
    //运行到此，为i==strlen(S)的情况
    return 0;
}
int main() {
    int add=sel("ababcabcacbab", "abcac");
    printf("%d",add);
    return 0;
}

时间复杂度

“BF” 算法在最理想的情况下的时间复杂度为O(m)( m 是模式串的长度，也就是第一次匹配就成功的情况)。

一般情况下，"BF"算法的时间复杂度为O(n+m)(n是主串的长度，m是模式串的长度)。

最坏的情况下的时间复杂度为O(nm)（例如主串 S 为“000000000001”，模式串 T ”001”,每次匹配时，直到匹配最后一个元素，才得知匹配失败，运行了 nm 次）。

KMP算法

串的普通模式匹配算法，大体思路是：模式串从主串的第一个字符开始匹配，每匹配失败，主串中记录匹配进度的指针 i 都要进行 i-j+1 的回退操作（这个过程称为“指针回溯”），同时模式串向后移动一个字符的位置。一次次的循环，直到匹配成功或者程序结束。

"KMP"算法相比于"BF"算法，优势在于：
在保证指针 i 不回溯的前提下，当匹配失败时，让模式串向右移动最大的距离；
并且可以在O(n+m)的时间数量级上完成对串的模式匹配操作；

故，"KMP"算法称为“快速模式匹配算法”。

next函数实现

#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
    int i=1;
    next[0]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}