多种字符串匹配算法杂谈

   平常操作文本的时候，经常需要操作对字符串进行操作。而字符串中最重要的一种操作就叫匹配，字符串的匹配算法很多，人们最熟悉的莫过于KMP算法了。今天就来谈一谈一些字符串匹配算法。

    先来说说大名鼎鼎的KMP算法，这个算法出现在无数的数据结构与算法书上面。它的策略很简单：当模式串第k个字符不匹配主串中第s时，我们其实己经知道了主串中s个字符前的k-1个字符是什么，于是利用这些信息，构造一个前k-1个字符的最长的前缀和后缀相同的一个位置，再从这个位置的下一个字符进行匹配。这也是我们经常求的next数组，对于next数组还有一个优化，那就是最长的串的后一个字符与第k个字符相同时，我们可以知道，那么下一次匹配肯定也不会成功，因为先前那一次我们己经知道这个位置的字符不是第s个字符了。这也就是经常说了nextval数组。它是在模式串中求得的，这里就不细说了，相信各位都己经很清楚，有兴趣的可以上网查查相关资料。

    但实际用到的呢？对于很多简单的查找程序来说，并没有使用KMP算法，而是使用的蛮力(brute-force)匹配，也就是传说中的暴力了。虽然KMP算法比蛮力匹配算法复杂度在大O标记下要高很多，但是一般来说差别并不大，所以现在许多简单的查找程序还是使用的蛮力，因为它实现起来非常简单。

    而受蛮力匹配算法的影响，又出现了一种叫BM的算法，它的模式在从右到左进行匹配的，与平常我们从左到右一个一个进行匹配又有点不相同。它比暴力算法又好在哪呢？因为在暴力的时候我们发现不匹配的时候是一个一个字符右移的，而BM算法不是，它通过不匹配位置的字符是否出现在模式串在来进行，比如主串一个字符C，与字符的某个位置进行比较发现不匹配，并且C不曾出现过在模式串中，那么在这之前的所有字符都不会匹配的，所以模式串肯定需要移动C前面的字符个数个位置！而不匹配时又出现在模式串中了呢？我们右移最右出现的位置的个数个，虽然不一定是最好的，但是能保证一定不会漏掉任何可能的匹配。

    还有一种多模式的匹配算法叫做AC自动机。它能一次匹配多个模式串。它与KMP的思路很像，不匹配时找一个最长的再继续进行！它需要先把字符串建成一颗Trie树，树结点有一个叫做failed的指针，是表示如果不匹配时应该再从哪个结点进行匹配。因为这种做法是一种DFA上的匹配，而发明这种算法的人叫A.C.，所以就叫AC自动机了。复杂度很好，比每个模式串用一次KMP算法要好很多。

    还有一种叫做后缀数组和后缀树的，后缀树是可以转发为后缀数组的，这两种构造起来很不简单，但是复杂度却是惊人的好。如求最长重复连续子串，出现次数最多的子串等都能用它完美的解决。有兴趣的可以搜搜，后缀数组的资料应该是比较多的，而后缀树由于太复杂，资料不是很多，还是有的。

    上面介绍的都是精确匹配的算法，其实对于字符串，还有一种模糊匹配，有兴趣的读者可以阅读一本叫做《柔性字符串匹配》的书，肯定会让你获益匪浅。

    字符串的匹配算法很多，也很有趣，如果你有什么有趣的匹配算法或者文本没有提到的，可以留言，相互交流一下。