41_KMP子串查找算法

关键词：

题目：如何在目标字符串S中查找是否存在子串P？

0. 朴素解法

思路：子串中的每一个字符与匹配字符串中的每一个字符一个个比较，如果相等，同时移动一位再比；如果不相等，则后移一位，从子串的第一个字符开始比较，直到找完全匹配的字符串为止。

int sub_str_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;
}

1. 朴素解法的优化

上图中因为pa != pb 且pb == sb，所以：pa!=sb。因此子串p右移1位去比较是否相等是没有意义的。

• 匹配失败时的右移位数与子串本身相关，与目标串无关；
• 移动位数 = 已匹配的字符数 - 对应的部分匹配值

• 任意子串都存在一个唯一的部分匹配表（pmt）

  
  部分匹配表示例

2. 获取部分匹配表

• 前缀：除了最后一个字符以外，一个字符串的全部头部组合
• 后缀：处理第一个字符以外，一个字符串的全部尾部组合

• 部分匹配值：前缀和后缀的最长共有元素的长度（前缀与后缀的交集的最大值）

  
  字符串"ABCDABD"部分匹配表示例

编程实现部分匹配表的关键步骤：

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

make_pmt()

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

    if( ret != NULL )
    {
        int ll = 0;     // 前缀、后缀的交集中的最大长度(longest length)

        ret[0] = 0;     // 下标为一的ll值为0

        for(int i=1; i<len; ++i)    // 确定剩下元素的ll值
        {
            while( (ll > 0) && (p[i] != p[ll]) )
            {
                ll = ret[ll - 1];
            }

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

            ret[i] = ll;
        }
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a pmt...");
    }

    return ret;
}

3. KMP子串查找

kmp算法

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

    if( (pmt != NULL) && (pl > 0) && (pl <= sl) )
    {
        for(int i=0, j=0; i<sl; ++i)
        {
            while( (j > 0) && (s[i] != p[j]) )  //如果匹配不成功，移动子串，查pmt表改变j的值
            {
                j = pmt[j - 1];
            }

            if(s[i] == p[j])    // 单个字符匹配相等， j加一
            {
                ++j;
            }

            if( j == pl )   // 相等的长度等于子串的长度， 则匹配完成
            {
                ret = i + 1 - pl;
                break;
            }
        }
    }

    free(pmt);

    return ret;
}

4. 小结

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

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4