青岛网络推广服务_咸阳网站建设工作室_电商关键词工具_seo引擎优化方案

KMP 串模式匹配算法

• In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
• 理解KMP算法有几个层次,第一个层次是认识朴素暴力的模式匹配算法的不足之处,针对该不足找到提高效率的突破口
• 第二个层次是找到通过探索找到系统的方法来描述这个加速的操作及其依赖的要素
• 第三个层次是优化和改进算法使其更适合编写为程序和细节的深刻认识

串的模式匹配算法——KMP 算法

暴力算法为什么慢

在暴力匹配中，每趟匹配失败都是模式串后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式串的某个前缀，这种频繁的重复比较相当于模式串不断地进行自我比较，这就是其低效率的根源。

因此，可以从分析模式串本身的结构着手，若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，则可将模式串向后滑动到与这些相等字符对齐的位置，主串 $i$ 指针无须回溯，并从该位置开始继续比较。

事实上,模式串向后滑动位数的计算仅与模式串本身的结构有关，而与主串无关

例如
$$\begin{array}{ccccc}{s}_t& s_{t+1}& \cdots & s_x& \stackrel{{\downarrow }^i}{\boxed{s_{x+1}}}\cdots \\ p_1& p_2& \cdots & p_j& \underset{{\uparrow }_j}{\boxed{p_{j+1}}}\cdots \end{array}$$
主串的$s_t\cdots s_x$和$p_1\cdots p_j$是对应相等的即$s_t\cdots s_x$=$p_1\cdots p_j$,而在$s_{x+1}\ne p_{j+1}$;也就是说此次匹配检查中有$j$个字符匹配上了

所以可以改写为
$$\begin{array}{ccccc}{p}_1& p_2& \cdots & p_j& \stackrel{{\downarrow }^i}{\boxed{s_{x+1}}}\cdots \\ p_1& p_2& \cdots & p_j& \underset{{\uparrow }_j}{\boxed{p_{j+1}}}\cdots \end{array}$$
由此可以看到,模式串向后滑动位数的计算仅与模式串本身的结构有关，而与主串无关

现在问题是模式串需要滑动到下一个位置继续比较,滑动偏移量应该如何确定?

显然偏移量越大越好,这样可以减少比较次数,尽快扫描完主串结束算法

为了便于理解,这里举几个例子

某个主串序列$abcabm\cdots$,模式串序列$abcabcn\cdots$;可以看到$abcab$是两个比较串共同的前缀,从$m\ne n$处开始失配($m,n$可以是任意不想等的两个字符,比如分别取$a,b$)

根据暴力匹配算法(回溯方法),可以得知模式串在最初失配的时候,模式串的第$3$次向右滑动(每次滑动一个位置)前都会失配,第三次滑动时能匹配上模式串的前缀$abc$,但是后续如何取决于$m$之后的序列
$$\begin{array}{ccccccccccc}\boxed{a}& b& c& \boxed{a}& b& m& \cdots & & & & \\ & & & a& b& c& a& b& c& n& \cdots \end{array}$$
可以看到即使仅根据已经匹配的部分模式串的子串$abcab$,就可以把模式串向后滑动若干位置,本例中是滑动了3个位置,但是这里还是用了回溯的方法来确定滑动位置数,后面有更好的方法,这里只是说明模式串和字串已经匹配上的头部字串可以利用起来

将这个结论记录起来,之后如果还遇到主串和模式串的头部匹配上的序列为$abcab$的情况,我们就可以直接滑动3个位置,依次类推,如果将可将所有模式串和主串匹配上的情况都列举出来,那么每次可以滑动的距离就可以直接查出来,做到不回溯

为了将问题具象化,我们把本例的模式串定为$T=abcabc$,它的长度为6,那么所有可能产生的部分匹配或全部匹配共有6种情况

这6种情况枚举出来就是头部子串集合 { a , a b , a b c , a b c a , a b c a b , a b c a b c } \set{a,ab,abc,abca,abcab,abcabc} {a,ab,abc,abca,abcab,abcabc}

对于$a$,滑动的距离只能是1

对于$ab$滑动的距离是$2$

…

又比如另一对主串和模式串$abcde$做匹配,某次匹配到的部分为$abcd$,那么在$m$处失配后,能够继续滑动4个位置得到以下结果
$$\begin{array}{ccccccccc}a& b& c& d& m& \cdots & & & \\ & & & & a& b& c& d& e\end{array}$$
同理,主串的后续部分如果又遇到了部分匹配$abcd$,那么可以不回溯将模式串向后移动$4$个位置

更一般的主串某个部分和模式串匹配上的部分为$p_1\cdots p_j$
$$\begin{array}{ccccc}{p}_1& \cdots & p_j& s_{j+1}& \cdots \\ p_1& \cdots & p_j& p_{j+1}& \cdots \end{array}$$
那么今根据匹配上的这部分内容,挖掘$p_1\cdots p_j$序列上的信息,

设$p_1\cdots p_{k_1}$=$p_{k_2}\cdots p_j$; ( k 1 , k 2 ∈ { 1 , ⋯ , j } ) (k_{1},k_{2}\in\set{1,\cdots,j}) (k1​,k2​∈{1,⋯,j}),设等式两边的串的长度为$L_k$,$k_1,k_2$可能有多个取值组合,但是能过作为偏移参考的只有使得$L_k$取最大值的那一组是我们关心的,后面我们默认$L_k$是最大的那一个,除非特别强调

这时,主串失配后的偏移量就是$L_k$的相关表达式:$j-L_k$,此时我们希望$L_k$越小越好

为了方便继续讨论,需要了解以下关于字串的概念,$L_k$,称为串$p_1\cdots p_j$的部分匹配值,后面我们会将其记为$PM(p_1\cdots p_j)=L_k$

字符串子串的相关概念

要了解子串的结构，首先要弄清楚几个概念：

前缀、后缀和部分匹配值。前两个在这里理解为串的集合

前缀和后缀

设串$S=s_1{s}_2{s}_3\cdots s_n$; 我们一这个一般性的形式化的串作为讨论对象

• 前缀指除最后一个字符以外，字符串的所有头部子串；
  • 串$S$的所有头部子串的通式可以描述为$s_1{s}_2\cdots s_x$,$(x=1,2,\cdots ,n-1)$
  • 则串$S$的前缀(头部子串集合)为$F(S)$= { s 1 ⋯ s x ∣ x = 1 , 2 , ⋯ , n − 1 } \set{s_{1}\cdots{s_{x}}|x=1,2,\cdots,n-1} {s1​⋯sx​∣x=1,2,⋯,n−1},共有$n-1$个元素,长度各不相同,$s_1\cdots s_x$的长度为$x$
• 后缀指除第一个字符外，字符串的所有尾部子串；
  • 串$S$的所有尾部子串的通式可以描述为$s_x{s}_{x+1}\cdots s_n$,$(x=2,\cdots ,n)$
  • 则串$S$的后缀(尾部子串集合)为$R(S)$= { s x ⋯ s n ∣ x = 2 , ⋯ , n } \set{s_{x}\cdots{s_{n}}|x=2,\cdots,n} {sx​⋯sn​∣x=2,⋯,n},共有$n-1$个元素,长度各不相同,$s_x\cdots s_n$的长度为$n-(x-1)$=$n-x+1$

为什么这里要约定前缀和后缀不包含串本身?这和前缀和后缀的应用有关,也就是用来计算串的部分匹配值,如果前后缀包含串本身,部分匹配值将失去意义,无法推进算法

部分匹配值(PM)

• 字符串的部分匹配值（Partial Match, PM）则为字符串的前缀和后缀的最长相等前后缀长度。
  • $U(S)$=$\max (\mathrm{P}(\mathrm{S})\cap \mathrm{R}(\mathrm{S}))$,这里的$\max (\mathrm{S})$表示求字符串集合中最长串元素的长度

部分匹配值序列(PM表)

对于给定字符串$S=s_1{s}_2\cdots s_n$,其不同的头部字串,以及其本身共有$n$个子串

分别计算$s_1\cdots s_x$,$(x=1,2,\cdots ,n)$的部分匹配值(PM),最后得出$n$个值,构成字符串$S$的部分匹配值序列(PM表)

PM表对于KMP算法中是核心内容,在模式串失配的时候应该往后滑动模式串多少位置就需要通过模式串的PM表来确定,例如$ababa$的PM值为3(最长公共前后缀为$abc$,其长度为3)

滑动位数计算公式

若模式匹配问题中,主串$S$和模式串$T$匹配上的部分为子串$C$,而在下一个字母处失配,那么就可以通过公式$D(C)=\mathrm{L}(\mathrm{C})-\mathrm{PM}(\mathrm{C})$求出需要移动的位数(其中$L(C),PM(C)$分别表示$C$串长和$C$的PM值)

可以看到,滑动位数计算公式仅用到了模式串$T$和主串$S$匹配上的这部分公共子串$C$,$C\subset T$,分别计算$C$的长度和部分匹配值做差就得到滑动位数,如果根据T的所有子串枚举出所有部分匹配值,就可以实现不回溯的快速模式匹配

例

下面以 ‘ababa’ 为例进行说明,它长度为5,可以写出5个头部子串(包括其本身)：

1. ‘$a$’ 的前缀和后缀都为空集，最长相等前后缀长度为 0。
2. ‘$ab$’ 的前缀为 { a } \{a\} {a}，后缀为 { b } \{b\} {b}， { a } ∩ { b } = ∅ \{a\} \cap \{b\} = \emptyset {a}∩{b}=∅，最长相等前后缀长度为 0。
3. ‘$aba$’ 的前缀为 { a , a b } \{a, ab\} {a,ab}，后缀为 { a , b a } \{a, ba\} {a,ba}， { a , a b } ∩ { a , b a } = { a } \{a, ab\} \cap \{a, ba\} = \{a\} {a,ab}∩{a,ba}={a}，最长相等前后缀长度为 1。
4. ‘$abab$’ 的前缀和后缀的交: { a , a b , a b a } ∩ \{a, ab, aba\} \cap {a,ab,aba}∩ { b , a b , b a b } = { a b } \{b, ab, bab\} = \{ab\} {b,ab,bab}={ab}，最长相等前后缀长度为 2。
5. ‘$ababa$’ 的前缀和后缀的交: { a , a b , a b a , a b a b } \{a, ab, aba, abab\} {a,ab,aba,abab} $\cap$ { a , b a , a b a , b a b a } = { a , a b a } \{a, ba, aba, baba\} = \{a, aba\} {a,ba,aba,baba}={a,aba}，公共元素有两个，最长相等前后缀长度为 3。

因此，字符串 ‘ababa’ 的部分匹配值序列为 00123。

小结

按照上述定义法求给定字符串的部分匹配值序列不是那么方便,首先要列出前缀集合和后缀集合，然后一 一对比两个集合中相同长度的串是否相等,得到交集,再要从交集中算出最长元素的长度

后面有更好的方法求给定字符串的部分匹配值序列,这里先考虑这个部分匹配值有什么作用

前面的章节已经给出铺垫,现在我们有合适的称呼来描述相关过程

应用示例

考虑主串为 ababcabcacbab，子串为 abcac的模式匹配问题

利用上述方法容易写出子串 ‘abcac’ 的部分匹配值为 00010，将部分匹配值写成数组形式，就得到了部分匹配值表(PM表)

编号(公共序列长度L)	1	2	3	4	5
S	a	b	c	a	c
PM	0	0	0	1	0
D	1	2	3	3	5

这里$D(C)=L(C)-PM(C)$,$C$表示模式串和主串匹配相等的序列串(有的地方少一样,这里为了方便加上最后一样,表示滑动位数)

这个表要如何理解和使用?

比如$L=3$列$(c,0)$,(编号不重要,重要的是头部字串)它表示串$abcac$的长度为3的头部子串$abc$的PM值为$0$说明$(PM(abc)=0)$,若某个匹配过程中发现模式串和主串匹配$abc$时都配上了,但是下一个字符失配,这时候需要移动的位置为$D(abc)=L(abc)-PM(abc)$=$3-0$=$3$
$$\begin{array}{cccccccc}a& b& c& m& \cdots & & & \\ \boxed{}& & & \boxed{a}& b& c& d& e\end{array}$$
上图所示,模式串从$\boxed{}\to \boxed{a}$移动了3个位置(位数)

完整步骤

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串	a	b	c

发现 c 与 a 不匹配，前面的 2 个字符 ab 是匹配的。查表可知，最后一个匹配字符 b 对应的部分匹配值为 0。

因此按照下面的公式算出子串需要向后移动的位数：

移动位数=已匹配的字符数-对应的部分匹配值

因为 $2-0=2$，所以将子串向后移动 2 位，如下进行第二趟匹配：

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串			a	b	c	a	c

发现 c 与 b 不匹配，前面 4 个字符 abca 是匹配的。最后一个匹配字符 a 对应的部分匹配值为 1。

因此按照下面的公式算出子串需要向后移动的位数：
$ \text{移动位数} = \text{已匹配的字符数} - \text{对应的部分匹配值} $

因为 $4-1=3$，所以将子串向后移动 3 位，如下进行第三趟匹配：

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串						a	b	c	a	c

算法时间复杂度

子串全部比较完成，匹配成功。整个匹配过程中，主串始终没有回退，所以KMP算法可以在$O(n+m)$的时间数量级上完成串的模式匹配操作，大大提高了匹配效率。

某趟发生失配时，若对应的部分匹配值为0，则表示已匹配相等序列中没有相等的前后缀，此时移动的位数最大，直接将子串首字符后移到主串当前位置进行下一趟比较

若已匹配相等序列中存在最大相等前后缀(部分匹配值非0)（可理解为首尾重合部分字符数量非0），则将子串向右滑动到和该相等前后缀对齐（这部分字符下一趟显然不需要比较），然后从主串当前位置进行下一趙比较。

小结

上述讨论已经把KMP算法的最核心内容:部分匹配值表(PM表)及其使用做了介绍

更近一步的问题是如何方便的求出PM序列