KMP 算法

发表于 更新于 分类于

KMP

　　KMP 算法是一种模板匹配算法，在字符串匹配中非常高效，时间复杂度为 , KMP 算法的核心在于 next 数组的构造, 即失配函数，当匹配不成功时当前模板应当向后移动的位数.
　　传统简单匹配算法效率低下的原因在于，当匹配失败时，仅仅是将模板向后移动一位继续匹配，没有从之前匹配过的模式中获取有用的信息.

暴力匹配算法

　　传统的模式匹配算法是将模板与字符串一一进行匹配，如果匹配成功，返回当前模板与字符串对应的开始位置；如果匹配失败，将模式字符串向后移动一位，继续进行匹配，由此可知最坏情况下的时间复杂度为 .

1
2
3
4
5
6
7
8
9
10
size_t strStr(const string& T, const string& P)
{
    size_t pos = 0;
    while (strncmp(T.c_str() + pos, P.c_str(), P.length()) not_eq 0 
            and pos < T.length() - P.length())
    {
        ++pos;
    }
    return pos == T.length() - P.length() ? string::npos : pos;
}

预备知识

  • 字符串的前缀
    从下标 0 开始的一段连续的字串，用 prefix(i) 表示字符串中 这个前缀
  • 字符串的后缀
    从任意下标开始到字符串结尾的一段连续字符串, 用 suffix(i) 表示字符串中 这段后缀
  • 两个串的最长公共前缀
    两个串的前缀中相等且最长的一组前缀

失配函数

　　KMP 先对模式字符串进行处理，得到一个 next 数组，又称失配函数.
　　next 表的每一位表示前缀和后缀集合中最长相同字串的字符数.
　　当发生失配时移动位数 = 已匹配的字符数 - 对应的 next 值

　　好麻烦啊