kmp算法复杂度o m?希尔排序算法?KMP算法学习总结

你是否正在寻找关于kmp算法的内容？让我把最实在的东西奉献给你：

0、废话

一直ym传说中的kmp算法能以最坏线性的时间复杂度搞定字符串匹配，

开始动手看才知道kmp中的K居然是Donald.E.Knuth，《计算机程序设计艺术》的作者。

好吧，继续ym……

1、传统的字符串匹配算法

/* * 从s中第sIndex位置开始匹配p * 若匹配成功，返回s中模式串p的起始index * 若匹配失败，返回-1 sIndex = 0) { int i = sIndex, j = 0; if (s.length() < 1 || p.length() < 1 || sIndex < 0) { return -1; } while (i != s.length() && j != p.length()) { if (s[i] == p[j]) { ++i; ++j; } else { i = i - j + 1; j = 0; } } return j == p.length() ? i - j: -1; }

2、传统字符串匹配算法的性能问题

用模式串P去匹配字符串S，在i=6,j=4时发生失配：

i=6

S: a b a bc a d c a c b a b

P: a bc a c

j=4

此时，按照传统算法，应当将P的第 1 个字符a(j=0)滑动到与S中第4个字符b(i=3) 对齐再进行匹配：

i=3

S:a b a bc a a d a c b a b

P: a bc a c

j=0

这个过程中，对字符串S的访问发生了“回朔”（从 i=6 移回到 i=3）。

我们不希望发生这样的回朔，而是试图通过尽可能的“向右滑动”模式串P，让P中index为 j 的字符对齐到S中 i=5 的字符，然后试图匹配S中i=6 的字符与P中index为 j+1 的字符。

在这个测试用例中，我们直接将P向右滑动3个字符，使S中 i=5 的字符与P中 j=0 的字符对齐，再匹配S中 i=6 的字符与P中 j=1 的字符。

i=6

S:a b a bc ad c a c b a b

P: a bc ac

j=0

3、kmp算法的一般性讨论

下面讨论在一般性的情况下，如何实现在“不回朔”访问S、仅依靠“滑动”P的前提下实现字符串匹配，即“kmp算法”。

i=6

S:a b a bc ad c a c b a b

P: abc ac

k=1

i=6

S: a b a bc ad c a c b a b

P: a bc ac

j=4

对于任意的S和P，当S中index为 i 的字符和P中index为 j 的字符失配时，我们假定应当滑动P使其index为 k 的字符与S中index为 i 的字符“对齐”并继续比较，。

那么，这个 k 是多少？

我们知道，所谓的对齐，就是要让S和P满足以下条件（上图中的蓝色字符）：

……（1）

另一方面，在失配时我们已经有了一些部分匹配结果（上图中的绿色字符）：

……（2）

由（1）、（2）可以得到：

……（3）

即如下图所示效果：

定义next[j]=k，k表示当模式串P中index为 j 的字符与主串S中index为 i 的字符发生失配时，应将P中index为 k 的字符继续与主串S中index为 i 的字符比较。

……（4）

按上述定义给出next数组的一个例子：

j 0 1 2 3 4 5 6 7

P a b a a b c a c

next[j] -1 0 0 1 1 2 0 1

在已知next数组的前提下，字符串匹配的步骤如下：

i 和 j 分别表示在主串S和模式串P中当前正待比较的字符的index，i 的初始值为sIndex，j 的初始值为0。

，i 和 j 分别增 1，

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-8680-1.html