【数据结构】41_KMP字串查找算法

c/c++

浏览数:58

2020-6-15

问题

如何在目标字符串 S 中,查找是否存在子串 P?

朴素解法

int sub_index(const char *s, const char* p)
{
    int ret = -1;
    int sl = strlen(s);
    int pl = strlen(p);
    int len = sl - pl;
    
    for (int i = 0; (ret < 0) && (i <= len); ++i)
    {
        bool equal = true;
        
        for (int j = 0; equal && (j<pl); ++j)
            equal = equal && (s[i + j] == p[j]);
            
        ret = (equal ? i : -1);
    }
    
    return ret;
}

朴素算法的一个线索优化

因为,pa != pb 且 pb == sb;
所以,Pa != sb;
结论,字串 p 右移 1 位比较,没有意义且低效

优化示例

伟大的发现: KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特莫里斯普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的

  • 匹配失败时的右移位数与子串本身相关,与目标串无关
  • 移动位数 = 已匹配的字符数 – 对应的部分匹配值
  • 任意字串都存在一个唯一的部分匹配表

部分匹配表示例

用法:

==> 第 7 位匹配失败
==> 前 6 位匹配成功
==> 查表PMT[6]
==> 右移位数 6 – PMT[6] = 6 – 2 = 4

问题:部分匹配表怎么得到?

关键概念

  • 前缀

    • 除了最后一个字符以外,一个字符串的全部头部组合
  • 后缀

    • 除了第一个字符以外,一个字符串的全部尾部组合
  • 部分匹配值

    • 前缀和后缀最长共有元素的长度

示例 :ABCDABD

字符 前缀 后缀 交集 匹配值
1 A 0
2 AB A B 0
3 ABC A,AB BC,C 0
4 ABCD A,AB,ABC BCD,CD,D 0
5 ABCDA A,AB,ABC,ABCD BCDA,CDA,DA,A A 1
6 ABCDAB A,AB,ABC,ABCD,ABCDA BCDAB,CDAB,DAB,AB,B AB 2
7 ABCDABD A,AB,ABC,ABCD,ABCDA,ABCDAB BCDABD,CDABD,DABD,ABD,BD,D 0

“ABCDABD” 部分匹配值为 2

问题: 怎样编程产生部分匹配表?

实现关键 (前辈经验)

  • (1) PMT[1] = 0 (下标为 0 的元素匹配值为 0)
  • (2) 从 2 个字符开始递推 (从下标为 1 的字符开始递推)
  • (3) 假设 PMT[n] = PMT[n – 1] + 1 (最长共有元素的长度)
  • (4) 当假设不成立, PMT[n] 在 PMT[n-1] 的基础上减少

示例 ababax

  • LL : longest length (前缀、后缀交集元素的最长长度)
  • (a) 当前要求的 LL 值通过历史 LL 值推导 (+1)
  • (b) 当可选的 LL 值为0,直接比较首首尾元素
  • (c) 将已匹配最长交集元素作为种子,分别向后扩展一个字符,比较扩展字符

分解:

(0) “a” LL = 0
第1个元素的LL值为0,即 PMT[1] = 0。

(1) “ab” LL = 0
从第1个元素开始推导,假设 PMT[2] = PMT[1] + 1;
判断假设是否成立:,当可选的LL值为0,直接比较首尾元素, a != b
假设不成立,所以 PMT[2] = 0;

(2) “aba” LL = 1
假设 PMT[3] = PMT[2] + 1;
判断假设是否成立:,当可选的LL值为0,直接比较首尾元素, a == a
假设成立,所以 PMT[3] = 0 + 1 = 1

(3) “abab” LL = 2
假设 PMT[4] = PMT[3] + 1;
判断假设是否成立: 将已匹配最长交集元素作为种子,分别向后扩展一个字符,比较扩展字符,a-> ab | a->ab
b == b 假设成立,所以 PMT[4] = 1 + 1 = 2

(4) “ababa” LL = 3
假设 PMT[5] = PMT[4] + 1;
判断假设是否成立: 将已匹配最长交集元素作为种子,分别向后扩展一个字符,比较扩展字符,ab-> aba | ab->aba
a == a 假设成立,所以 PMT[5] = 2 + 1 = 3

(5) “ababax” LL = 0
假设 PMT[6] = PMT[5] + 1;
判断假设是否成立: 已匹配最长交集元素作为种子,分别向后扩展一个字符,比较扩展字符,aba-> abab | aba->abax
b != x 假设不成立;
==> 将已匹配最长交集元素最为总支再次尝试匹配
“aba|b” “aba|x” ==> “aba” ==> LL1 = PMT(3) = 1; ==> 交集元素 “a”
将已匹配最长交集元素作为种子,分别向后扩展一个字符,比较扩展字符:a-> ab | a->ax;
b != x 匹配失败
==> 将已匹配最长交集元素最为总支再次尝试匹配
“a|b” “a|x” ==> “a” ==> LL2 = PMT(1) = 0; 【尝试匹配结束条件】
当可选的LL值为0,直接比较首尾元素, a != x, 所以PMT[6] = 0

编程实验:部分匹配表的递推与实现

文件:main.cpp

#include <iostream>
#include <cstring>

using namespace std;

int *make_pmt(const char *s)
{
    size_t len = strlen(s);
    int *ret = static_cast<int*>(malloc(sizeof(int) * len));

    if (ret != nullptr)
    {
        int ll = 0;

        // 第0个元素的ll值为0
        ret[0] = 0;

        for (size_t i=1; i<len; ++i)
        {
            // 假设不成功时,再次尝试扩展
            while ((ll > 0) && (s[i] != s[ll]))
            {
                ll = ret[ll - 1];
            }

            // 对首尾字符或者扩展后的字符进行判断
            if (s[i] == s[ll])
            {
                // 假设成功时,ll自加
                ++ll;
            }

            ret[i] = ll;
        }
    }

    return ret;
}

int main()
{
    int * pmt = make_pmt("ababax");

    for (size_t i=0; i<strlen("ababax"); ++i)
    {
        cout << "i" << ":" << pmt[i] << endl;
    }

    free(pmt);
    
    return 0;
}

输出:

i:0
i:0
i:1
i:2
i:3
i:0

部分匹配表的使用 (KMP算法)

==> 下标 j 处匹配失败
==> 前 j 位匹配成功
==> 查表 PMT[j-1]
==> 右移位数 j – PMT[j-1]

因为, S[i] != p[j]
所以,查表, LL = PMT[j – 1]
于是,右移,i 的值不变, j 的值改变, j = j – (j – LL) = LL = PMT[j-1]

编程实验: KMP 字串查找算法的实现

文件:main.cpp

#include <iostream>
#include <cstring>

using namespace std;

int *make_pmt(const char *p)  // O(m)
{
    size_t len = strlen(p);
    int *ret = static_cast<int*>(malloc(sizeof(int) * len));

    if (ret != nullptr)
    {
        int ll = 0;

        // 第0个元素的ll值为0
        ret[0] = 0;

        for (size_t i=1; i<len; ++i)
        {
            // 假设不成功时,再次尝试扩展
            while ((ll > 0) && (p[i] != p[ll]))
            {
                ll = ret[ll - 1];
            }

            // 对首尾字符或者扩展后的字符进行判断
            if (p[i] == p[ll])
            {
                // 假设成功时,ll自加
                ++ll;
            }

            ret[i] = ll;
        }
    }

    return ret;
}

int kmp(const char *s, const char *p)  // O(m + n)
{
   int ret = -1;
   int sl = strlen(s);
   int pl = strlen(p);
   int *pmt = make_pmt(p);  // O(m)

   if ((pmt != nullptr) && (0 < pl) &&(pl <= sl))
   {
       for (int i=0, j = 0; i < sl; ++i)  // O(n)
       {
           while ((j > 0) && (s[i] != p[j]))
           {
               j = pmt[j - 1];  // j = j - (j - LL) = LL = PMT[j-1];
           }

           if (s[i] == p[j])
           {
               ++j;
           }

           if (j == pl)
           {
               ret = i + 1 - pl;
               break;
           }
       }
   }

   free(pmt);

   return ret;
}

int main()
{
    cout << kmp("abcde", "cde") << endl;
    cout << kmp("abcde", "") << endl;
    cout << kmp("abcde", "a") << endl;
    cout << kmp("abcde", "bc") << endl;

    return 0;
}

输出:

2
-1
0
1

小结

  • 部分匹配表是提高字串查找效率的关键
  • 部分匹配值定义为前缀和后缀最长共有元素的长度
  • 可以用递推的方法产生部分匹配表
  • KMP 利用部分匹配值与字串移动位数的关系提高查找效率

以上内容整理于狄泰软件学院系列课程,请大家保护原创!

作者:TianSong