算法目的

​ 确定主串中所含子串（模式串）第一次出现的位置（定位）

算法应用

  • 搜索引擎、拼写检查、语言翻译、数据压缩

算法种类

  • BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）
  • KMP算法（特点：速度快）

BF算法

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举法的思路

  • 将主串的第pos个字符和模式串的第一个字符比较
    • 若相等，继续逐个比较后续字符；
    • 若不等，从主串的下一字符起，重新与模式串的第一个字符比较。
    • 直到主串的一个连续子串字符序列和模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
    • 否则，匹配失败，返回值为0.
int index_BF(SString S,SString T){
    int i=1,j=1;
    while (i<=S.length &&j<=T.length){
        if(s.ch[i]==t.ch[j]){++i;++j;}//主串和子串依次匹配下一个字符
        else{i=i-j+2;j=1;}//主串、子串指针回溯重新开始下一次匹配
    }
    if(j>=T.length) return i-T.length;//返回匹配的第一个字符的下标
    else return 0;//模式匹配不成功
}
BF算法时间复杂度

例：S='0000000001',T='0001',poS=1
若n为主串长度，m为子串长度，最坏情况是

  • 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次

  • 最后m位也各比较了1次

    总次数为：(n-m) * m+m=(n-m+1)*m

    若m<<n,则算法复杂度O(n*m)

KMP (Knuth Morris Pratt)算法

​ KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法

算法设计思路：利用已经部分匹配的结果而加快模式串的滑动速度?

且主串S的指针i不必回溯！可提速到O(n+m)