分享程序员开发的那些事...
更新时间：2022-09-21 19:24:08
模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
文中代码是本人自己写的，实测有效，含JAVA和C++两种代码。干货充足吧。
蛮力算法(Brute-Force)，简称BF算法。（男朋友算法，简单粗暴—_—!）
算法思想
BF算法的算法思想是：
从目标串T的的第一个字符起与模式串P的第一个字符比较。
若相等，则继续对字符进行后续的比较；否则目标串从第二个字符起与模式串的第一个字符重新比较。
直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。
通过下图示例，可一目了然：
算法性能
假设模式串的长度是m，目标串的长度是n。
最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍。
总的比较次数最多为m(n-m+1)，因此BF算法的时间复杂度为O(mn)。
BF算法中存在回溯，这影响到效率，因而在实际应用中很少采用。
代码
JAVA版本
C++版本
运行结果
Knuth-Morris-Pratt算法（简称KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法，消除了BF算法中回溯问题，完成串的模式匹配。
算法思想
显然，移回到前面已经比较过的位置，还是不能完全匹配。
KMP算法的思想是，设法利用这个已知信息，跳过前面已经比较过的位置，继续把它向后移，这样就提高了效率。
由此可知，KMP算法其实有两大要点：
(1) 计算跳转位置信息，这里我们称之为部分匹配表。
(2) 后移到指定位置，重新开始匹配。
首先，来看如何获得部分匹配表。
这个next 数组叫做部分匹配表。
对于next[]数组的定义如下：
对于BF算法中的例子，模式串P=“abcac”，根剧next[j]的定义，可得到下表：
| j | 0 | 1 | 2 | 3 | 4 |
| t[j] | a | b | c | a | c |
| next[j] | -1 | 0 | 0 | 0 | 1 |
有了部分匹配表，就可以后移到指定位置
如果next[j] >= 0，则目标串的指针 i 不变，将模式串的指针 j 移动到 next[j] 的位置继续进行匹配；
若next[j] = -1，则将 i 右移1位，并将 j 置0，继续进行比较。
以上要点配合下面的示意图理解，效果会更好哦。
算法性能
在KMP算法中求next数组的时间复杂度为O(m)，在后面的匹配中因目标串T的下标不用回溯，所以比较次数可记为n。
由此，得出KMP算法的总的时间复杂度为O(n+m)。
代码
JAVA版本
运行结果
本文转自静默虚空博客园博客，原文链接：http://www.cnblogs.com/jingmoxukong/p/4343770.html，如需转载请自行联系原作者