字符串常见算法之一：查找一个短串在一个长串中位置

介绍的一些字符串处理的问题在日常编程中比较常见，但是在大学读书的时候几乎一个都没有涉及，最近学习了一下在这里介绍给大家，仅供参考。

这些算法与内容包括：

1、    查找一个短串在一个长串中位置；
2、    查找一个字符串中最长的重复子串；
3、    查找一个字符串中重复最多的子串；
4、    两个字符串最长的公共子串（连续）；
5、    两个字符串最长的公共子序列（不连续）；
6、    介绍一种强大的数据结构，Suffix tree.

这里有一个PPT：
http://www.cppblog.com/Files/humanchao/StringAlg.zip

-------------------------------------------------

查找一个短串在一个长串中位置

这个问题传统的解法时间复杂度为O(m*n)，m、n为两个串的长度。有一个Sunday算法，可以最大限度的优化这个比较过程，原理如下：

1、建立一个hash table，依次把search各个字符值作为table索引，为table相应的位置一个值（表示字符存在），如果出现重复，后面的位置会覆盖前面的位置。
例：我们要在"WHICH-FINALLY-HALTS.—AT-THAT-POINT"（简称string）查找" AT-THAT "（简称pat），刚开始时，把pat与string对齐，查看串string中与串pat 相对应的字符（F），在pat的位置，这个查找的过程时间复杂度通过hash table的下标索引为 O(1)：

2、如果发现没有，说明字符F之前已经无法与pat匹配，直接跳到position(F)+stringlength(pat)

3、发现”-”在pat位置3，于是重新定位对齐两串为：

4、倒序（从最后一个向前）比较两串，发现无法匹配，继续跳转->查找->定位
因为上面已经有一个T匹配成功，这次要从HALTS的S来查找，于是定位为：

5、上图无法匹配，从”--AT-“中A后的”-”继续查找，重复上过程，最终匹配如图：

这个算法关键点：
1、建立为pat建立hash表，以提高查找字符的速度；
2、对齐跳转，快速的后移比较，使比较次数减少。

具体的代码实现可以参考链接：

http://blog.csdn.net/unicode1985/archive/2007/05/30/1631038.aspx

posted on 2009-11-25 17:20 胡满超阅读(3118) 评论(0) 编辑收藏引用

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

最新随笔

最新评论

阅读排行榜

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理