字符串匹配算法

本文主要是介绍字符串匹配算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

BF算法

bf算法(brute force)顾名思义，是很暴力，很朴素的算法，我们把想要匹配的字符串叫做模式串，通俗理解来说就是模板，把被进行搜索来查找有无匹配的子串的字符串叫做主串。

bf算法是这样的：假设主串长度为n，模式串的长度对我们从主串的初始位置0开始，每次查找长度为m的字符串，直到找到匹配的字符串或者最多查找了n - m + 1次结束。

为什么说最多只会查找n - m + 1呢？从图中就能看出来了，当比较到了n - m次时，这时主串中还没有被比较过的字符就只剩下m个了，你顶多只能再比较一次，所以最多只能是n - m + 1次。

bf算法在极端情况下，比如，主串是一大串a，而子串是aaab，那么每次比较m个字符，比较n - m + 1次，会有时间复杂度O(n * m)，这看起来很高，但是事实上，我们可以每次比较时一旦遇到不匹配的字符就停下当次比较，而且实际开发遇到的主串和模式串一般不会很长，所以其实大部分情况下，执行效率都会比这个O(n * m)高很多，并且bf算法暴力朴素，不容易出错，即便有出错也更容易排查出来，在工程中，满足性能的情况下，简单是首选，这也是KISS设计原则(keep it simple and stupid)所以，bf算法还是很常用的。

RK算法（Rabin - Karp）

rk算法以它的两位发明者进行命名，该算法其实是在暴力匹配算法的基础上配合哈希算法使用。

为什么要配合上哈希算法使用呢，这是因为暴力匹配算法时间复杂度并不是很低，所以我们将主串的每个子串先转为哈希值（注意要考虑哈希值冲突，但我们这个例子中的哈希算法，对于不同字符串，哈希值是不同的，没有冲突），然后把模式串的哈希值与各个子串比较，如果相等，就证明匹配成功。并且由于哈希值是数字，所以比较会很迅速。

当然啦，这样的话匹配算法的复杂度不仅受哈希值比较影响，还会受哈希函数把字符串转化为哈希值的计算速度的影响，所以我们还要选择合适的哈希函数。

假设我们要操作的字符串集含有K个字符，那么我们可以用K进制来代替字符串。

比如我们可以假设我们操作的字符集只含有a~z26个字母，那么我们就可以用26进制，a对应1，b对应2.....这样对应下去，这时由于进制达到了两位数，所以将子串转化成十进制数，这个十进制数来当哈希值就可以了。转化的方式还是“乘权求和”。

并且你会发现，子串与子串之间的哈希值是大部分都重叠的，对于S[i - 1]和S[i]两个相邻子串来说，S[i]的哈希值按权展开的形式是S[i] 的按权展开的基础上，去掉最大的，然后整体乘基数的一次方，再加上S[i]的最后一个字符的下一个字符的值。

所以我们可以得出每个子串的的哈希值公式。

而且，还要注意，基数的各个次幂被反复使用且不被更改，所以我们提早算好，然后储存在一个数组中，当需要的时候，直接按下标读取就可以了，节省了很多时间。要是我们需要自己设置26个字母的值，26个字母对应的值也可以这样处理。

如果就看上面的例子，RK算法的时间复杂度包含了遍历字符串计算子串哈希值和比较所有子串和模式串，也就是O（n） + O（n） == O（2n）== O（n）。

但是，我们还要注意，哈希值是用整数存储的，所以有可能出现数值溢出，那么我们可以把字符串的每个字母全部加起来，加起来的值来当哈希值，这样溢出的概率就小得多了，当然，这会造成哈希冲突，所以我们这时的比较，当哈希值相同后，还要再比较以便子串和模式串本身，才能判断相不相同，极端情况下，会每一次都要在比较本身，也就是退化回了暴力匹配算法的时间复杂度，不过这也不多见，总体上，RK算法还是比BF算法效率高。

而且这是一种最简单的设计方法而已，还有许多的优化方法可以使哈希冲突概率更小，比如将每一个字母从小到大对应一个素数。

Trie树

trie树，本质就是把字符串按字符分类，即把字符串的公共前缀提取出来。我们用搜索引擎时，当打出一些字后，会出现一堆相关的字符串，这就是利用trie树完成的

假设我们有how，hi，her，hello，so，see这六个字符串，那么trie树的建立过程如下

trie树根节点不存储数据，树中每条从根节点到达红色节点的路径完全匹配某个字符串。

如果我们要查找某个字符串，那就先把字符串分割成一个个字符，从第一个字符开始匹配，比如her，那就是先从h开始，然后找到e，再找到r，如果只是he，那么就是先h，然后找到e。

从图中我们可以看出，trie树不是只能查找完全匹配的字符串，他还可以只查找部分匹配的字符串，这意味着什么，我们知道BF算法和RK算法的话如果要详细搜索某一字符串，要完完整整地给它打出来，然后才能作为模板，可是trie树就只需要你打出部分字符串就有机会猜到你想找的字符串，正是这个特性使得它能在搜索引擎中大放异彩。

如何实现一棵Trie树?

要想实现某个数据结构，肯定还是先分析出它要实现什么操作以及怎么样存储。

Trie树的操作其实就是两个：把字符串加到树中，另一个是匹配字符串。

Trie树是多叉树，它的存储我们可以参考二叉树，二叉树是由左右两个指针来连接父节点和子节点，那么多叉树可以仿照这个思路，把子节点的指针放到一个数组。

这个数组是有讲究的，放得好才能方便匹配，假设我们现在字符串集里只有a~z26个英文字母，那么我们先把根节点指向其子节点组成的数组，这个数组0下标代表a，1下标代表b，这样递推下去，然后每个元素（即每个节点）都储存自己的子节点数组，然后由这个数组开始，如果我们可以通过子节点与父节点之间的ASCII码差值来确定某个字符该放的位置，比如我们现在第一个字符是a，第二个字符是d，它们的ASCII码差值是3，那么我们可以把d放在数组下标为3的内存，这样一下就能知道主串里面的a是否有与模式串的a的下一个字符所匹配的子节点（字符）。

这样的话Trie树在加入字符串的时候要遍历所有要加入字符串，时间复杂度是O（n），但在查询时，设查询的字符串的长度为k那么就是O(k * 1)，，也就是O（k），除非你想查询的字符串长度非常非常大，不然就相当于O（1）的时间复杂度，会有很高的效率。

Trie树的内存消耗

我们可以看到，当重复前缀多的时候，Trie树省内存，但是重复前缀不多的时候，那么Trie树就很耗费内存了。

我们可以把每个节点指向的子节点数组不预先设置好，而且每有一个新字符串加入，才加到子节点数组，那么子节点数组保存的都是实际存在的数据了，查询时通过二分查找可以很快，但是插入时就会慢一些。

我们还可以用跳表，红黑树，散列表等等来代替普通数组去保存子节点。

Trie适用场景

在刚刚讲的这个场景，在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有极其严苛的要求。

第一，字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。

第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。

第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。

第四，我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综合这几点，针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，我们都不需要自己去实现，直接利用编程语言中提供的现成类库就行了。

但是这不代表Trie没用，实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串，比如搜索引擎中，你打出部分字符就能出现一堆可能是你想要查找的字符串的情况，还有自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

这篇关于字符串匹配算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！