串的模式匹配（BF算法，KMP算法）

约定不等于承诺〃 2022-08-22 04:00 204阅读 0赞

模式匹配(Pattern Matching) 即子串定位运算（Index函数）。

算法目的：确定主串中所含子串第一次出现的位置（定位） ——即如何实现 Index(S,T,pos)函数

初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(s)

操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符起第一次出现的位置；否则函数值为0。

注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”，否则称 “匹配不成功” 。

![20160524104427462][]

**BF算法**

BF算法设计思想：

将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .

例如： S=‘a b a b c a b c a c b a b’  T=‘a b c a c’ 返回pos=6

Int Index (SString S, SString T, int pos) \{

i=pos; j=1;

while ( i<=S\[0\] && j<=T\[0\] ) \{

if (S\[i\] = = T\[j\] ) \{++i, ++j\} //继续比较后续字符

else \{ i=i-j+2; j=1; \} //指针回溯到 下一首位，重新开始匹配

\} if(j>T\[0\]) //子串结束，说明匹配成功

return i-T\[0\]; // 匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。

else return0;

\}//Index

若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)\*m＝O(n\*m)

最恶劣情况是：主串中前面n-m+1个位置都部分匹配到子串的最后一位时出现不等，此时需要将指针i回溯，并从模式的第一个字符开始重新比较，每趟整个匹配过程中， while 循环执行m次，则总的while循环次数为(n-m+1)\*m。

但一般情况下BF算法的时间复杂度为O(n+m)

**KMP算法**

**![20160524104515619][]  
![20160524104546619][]  
![20160524104608463][]  
![20160524104625916][]**

**求解next\[j\] 算法:**

第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。  
![20160524104659902][]

详细解析：

当i=1时，j=0

当i=2时，j=1

当i=3时，看i的前一位即2的值为b，next值为1对应的内容是a，不相等，a的next值为0，所以j=1；

当i=4时，看i的前一位即3的值为a，next值为1对应的内容是a，相等 ，j=3的next值加1，所以j=2；

当i=5时，看i的前一位即4的值为a，next值为2对应的内容是b，不相等，再看2的next值1，对应的内容为a，与4相等，所以j=2的next值加1，所以j=2；

当i=6时，看i的前一位即5的值为b，next值为2对应的内容是b，相等，所以j=5的next值加1，为6

当i=7时，看i的前一位即6的值为c，next值为3对应的内容为a，不相等，3的next值为1对应的内容为a，不相等，所以j=1；

当i=8时，看i的前一位即7的值为a，next值为1对应的内容为a，所以j=7的next值加1，为2

next \[ j \]是否完美无缺？

答：未必，例如当 S=‘a b a a a a b’,T=‘a a a a b’时,仍有多余动作

![20160524104722825][]  
![20160524104743466][]

详细解析：

求nextval的值，是建立在求next值的基础上的。

当i=1时，nextval\[1\]的值为0；

当i=2时，2的值为a，2的next值为1对应的内容为a，相等，所以2的nextval\[2\]的值，继承nextval\[1\]的值为0；

当i=3时，3的值为a，3的next值为2对应的内容为a，相等，所以3的nextval\[3\]的值，继承nextval\[2\]的值为0；

当i=4时，4的值为a，4的next值为3对应的内容为a，相等，所以4的nextval\[4\]的值，继承nextval\[3\]的值为0；

当i=5时，5的值为b，5的next值为4对应的内容为a，不相等，所以5的nextval\[5\]的值，与其next值相等，为4

下面给出一个长的，加深印象。  
123456789……  
abcaabbabcabaacbacba  
next: 01112231234532211211  
nextval: 01102130110532210210

**KMP算法的时间复杂度**

回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)\*m＝O(n\*m)

而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算next\[j\]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法。

注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m),所以至今仍被采用。

KMP算法的用途：

因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！

[20160524104427462]: /images/20220722/6d8714350eac41b5a19622267bba8405.png
[20160524104515619]: /images/20220722/bb84283ad174400699dfe22225ef1161.png
[20160524104546619]: /images/20220722/0eb06fb301494dbe8a460c19b0bf8b11.png
[20160524104608463]: /images/20220722/fae403ca689041b085a007369207fd39.png
[20160524104625916]: /images/20220722/c2e4d468338148aba502c436fd0cdc4b.png
[20160524104659902]: /images/20220722/abfa39df2c944d8c94d58584c7a93d02.png
[20160524104722825]: /images/20220722/7686be1e6cbb4a21a61d00a067b956ed.png
[20160524104743466]: /images/20220722/c70686548bcc4f0eaec94985f284a597.png