从BF算法到kmp算法详解

正文索引
一、KMP介绍
二、例子：子串匹配母串
1.BF算法的解决方法
三、kmp算法的实现
（1）为什么已经有BF算法了还要有KMP算法呢？
（2）发明的算法基本思想
（3）具体实现

一、KMP介绍

KMP算法是一种改进的字符串匹配算法（有BF算法改进而来，BF算法是暴利搜索匹配的方式，而KMP则是对BF算法的回溯过程进行改进，从而大幅度降低了时间复杂度），能够很好地处理子串与母串的匹配

二、例子：子串匹配母串
母串：a b a a c a b a b c a c
子串：a b a b c

要求子串与母串进行匹配，求解在哪一个位置匹配上了。

1.BF算法的解决方法

关键词：逐一匹配 暴力搜索

第一步匹配

母串：a b a a c a b a b c a c
子串：a b a b c
匹配结果：第四个位置匹配失败

第二步匹配

母串：a b a a c a b a b c a c
子串： a b a b c
匹配结果：第一个匹配位置失败

第三步匹配

母串：a b a a c a b a b c a c
子串： a b a b c
匹配结果：第二个位置匹配失败

第四个位置

母串：a b a a c a b a b c a c
子串： a b a b c
匹配结果：第二个位置匹配失败

第五个位置

母串：a b a a c a b a b c a c
子串： a b a b c
匹配结果：第一个位置匹配失败

第六个位置

母串：a b a a c a b a b c a c
子串： a b a b c
匹配结果：匹配成功，返回位置6

以上就是BF算法的匹配过程，逐一移动，每个位置都尝试一遍

i 回溯到开始位置+1

j 回溯到子串的0位置

推理过程：j的长度实际上等于i向左移动的位置，那么要返回开始的位置再加1就可以表示成 i - j + 1

int BFstring(string MotherStr, string SonStr){
    int i = 0, j = 0;
    for(;(i != MotherStr.size()) && (j != SonStr.size());){
        if(MotherStr[i] == SonStr[j]){
            i++, j++;
        }
        else{
            i = i - j + 1;
            j = 0;
        }
        if(j == SonStr.size()){
            return i - j + 1;
        }

    }
    return 0;
}

int BFchar(char MotherStr[],char SonStr[]){
    int i, j;
	i = 0;//主串指针
	j = 0;//子串指针
	while (MotherStr[i] != '