串的模式匹配的几种方法

串的模式匹配

1. Brute Force(BF或蛮力搜索) 算法：

首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。

速度最慢。

2. KMP算法

利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离

比如

模式串ababac 这个时候我们发现在c 处不匹配，然后我们看c 前面那串字符串的最大相等前后缀，然后再来移动

下面的两个都是模式串，没有写出来匹配串

原始位置 ababa c

移动之后 aba bac

因为后缀是已经匹配了的，而前缀和后缀是相等的，所以直接把前缀移动到原来后缀处，再从原来的c 处，也就是现在的第二个b 处进行比较。 这就是KMP 。

3. Horspool算法

Horspool 算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大，为后来的算法影响很大。

匹配串：abcbc sdxzcxx

模式串：cbcac

这个时候我们从右向左进行对暗号，c-c ，对上了，第二个b-a ，不对，于是，模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符b 的位置，发现有，赶快对上匹配串：abcbcsd xzcxx 模式串： cbcac

然后继续从最右边的字符从右向左进行比较。这时候，我们发现了，d-c 不匹配，而且模式穿里面没有，没办法，只好移动一个模式串长度的单位了。

匹配串：abcbcsdxzcxx

模式串： cbcac

4. Boyer-Moore算法

是一个很复杂的算法，当然，虽然理论上时间复杂度和KMP 差不多，但是实际上却比KMP 快数倍。

分为两步预处理，第一个是bad-character heuristics ，也就是当出现错误匹配的时候，移位，基本上就是做的Horspool 那一套。

第二个就是good-suffix heuristics ，当出现错误匹配的时候，还要从不匹配点向左看，以前匹配的那段子字符串是不是在模式串本身中还有重复的，有重复的话，那么就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较

匹配串：abaccba bbazz 模式串：cbadcba 我们看到已经匹配好了cba ，但是c-d 不匹配，这个时候我们可以使用good-suffix heuristics

匹配串：abaccbabbaz z 模式串： cbadcba

可是，我们有时候也发现，已经匹配好的那一部分其实并没有再有重复了。这个时候，我们发现已经匹配好的那串字符串有一部分在开头重新出现了，那么，赶快，对齐吧。

匹配串：abacccb bbazz

模式串：cbadccb

然后得到

匹配串：abacccbbbazz

模式串： cbadccb

当两种Good-Suffix 出现的时候，取移动距离最大的那个。

5. Sunday算法

Sunday 的算法思想和Horspool 有些相似，但是。当出现不匹配的时候，却不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右边对齐的右一位的那个字符在模式串的位置。

比如：

匹配串：abcbc zdxzc 模式串：zbcac 恩，这里我们看到b-a 没有对上，我们就看匹配串中的z 在模式串的位置。

匹配串：abcbczdxzc

模式串： zbcac

如果模式串中的没有那个字符怎么办呢？很简单，跳过去呗。

匹配串：abcbc edxzcs 模式串：zbcac e 不在模式串中出现 那么我们就 匹配串：abcbcedxzcs 模式串： zbcac 6.应用

文本编辑

文本编辑程序用于源程序的输入和修改，公文书信，报刊和书籍的编辑排版等。常用的编辑文本程序有word,wps等。文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找，插入，删除等。