Chinaunix首页 | 论坛 | 博客
  • 博客访问: 190492
  • 博文数量: 21
  • 博客积分: 1263
  • 博客等级: 准尉
  • 技术积分: 697
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-24 00:05
个人简介

专注于Answers Ranking, Answer Monitor和log处理。

文章分类
文章存档

2014年(5)

2012年(16)

分类: C/C++

2012-06-12 14:28:57

   平常操作文本的时候,经常需要操作对字符串进行操作。而字符串中最重要的一种操作就叫匹配,字符串的匹配算法很多,人们最熟悉的莫过于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算法要好很多。

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

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

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

阅读(10674) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册