请查看原文:
http://www.ibaiyang.org/2012/03/25/repeat-substring/
最近在看《编程珠玑》,很多人说,应该看看这本神书,于是跟风,我也买了一本,不过才拿到这本书的时候,觉得也是一般,前面几章的例题很是一般,而且感觉作者分析的东西自己不是很实用,比如二分搜索就讲了2,3章,虽然作者对二份搜索的理解与实现,吹毛求疵,但是整体上来说,觉得没有意思,没有给人一张豁然开朗的感觉,在看到第二章时,讲到了变位词的算法,才令人痴迷,于是我疯狂的继续看下去,今天看到了重复字符串的实现方式,我高兴的立刻想发篇博文,来证实它多么的奇妙。
求一个字符串的最长重复字符串,就是在一个长字符串中,找出有重复的字符串,且其长度最长,我感觉这个题的引申意义也很大,特别在如今搜索引擎的时代。例如banana的最长字符串是ana,tian xian的最长字符串是ian。好了,看看是怎么实现的吧。
int cmp_str(char* p, char* q)
{
int size = 0;
while(p && q && *p == *q){
size++;
p++;
q++;
}
return size;
}
int maxlen = -1;
int current_size = -1;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if( (current_size = cmp_str(&input_string[i], &input_string[j]) ) > maxlen ){
maxlen = current_size;
low_index = i;
high_index = j;
}
}
}
其中最大的字符串长度存在原字符串中的i到j的位置,当然这是任何人都能想到的2B算法,我也包括在列,哎,继续努力吧。
那么,作者怎么看待这个问题的呢,其中用到了“后缀数组”,很早之前,就听某位ACM队员将过后缀数组,但是不知道他说的是什么,也没有追问,今天碰巧又遇到了它,冤家路窄啊。
什么是后缀数组呢,其实很简单,我觉得这个属于程序预处理部分,一个简单的数据结构。
这个结构是一个字符指针数组,假设记为word。读取字符时,我们对word进行初始化,使得每个元素指向输入字符串中的相应字符
int i = 0;
char ch;
while( (ch = cin.get()) != '\n' ){
input_string[i] = ch;
word[i++] = &input_string[i];
max_word++;
}
input_string[i] = '\0';
word[i] = NULL;
那么举个例子吧,如我们输入的字符串是baiyang,则
word[0] = "baiyang";
word[1] = "aiyang";
word[2] = "iyang";
word[3] = "yang";
word[4] = "ang";
word[5] = "ng";
word[6] = "g";
这些就成为“后缀数组”,如果你能理解二叉树,我相信这个也能理解吧。
如果某个长字符串在数组中出现二次,那么它将出现在二个不同的后缀中,因此我们队数组排序以寻找相同的后缀。
如对banana的后缀数组排序为
word[0] = "a";
word[1] = "ana";
word[2] = "anana";
word[3] = "banana";
word[4] = "na";
word[5] = "nana";
于是看到ana为最长,分别存在1,2二个后缀数组中。
当我们对后缀数组排好序之后,我们就可以遍历数组了
int i = 0;
int index = -1;
int max_len = -1;
int current_size = 0;
for(i = 0; i < max_word - 1; i++) { if( (current_size = cmp_str(word[i], word[i+1])) > max_len ) {
max_len = current_size;
index = i;
}
}
这样,最长的子字符串的长度就是max_len了,而起点就是index位置。故解决,算法复杂度由之前的n平方,降到了nlog(n)了。不过我觉得其中的后缀数组结构值得我们思考一下。
转载:http://www.ibaiyang.org/2012/03/25/repeat-substring/ 支持正版
-----------------打造高质量的文章 更多关注 把酒泯恩仇---------------
为了打造高质量的文章,请 推荐 一下吧。。。。谢谢了,请关注我后续的文章,会更精彩哦
请关注sina微博:http://weibo.com/baiyang26
把酒泯恩仇官方博客:http://www.ibaiyang.org 【推荐用google reader订阅】
把酒泯恩仇官方豆瓣:http://www.douban.com/people/baiyang26/
如果您想转载本博客,请注明出处
如果您对本文有意见或者建议,欢迎留言
分享到:
相关推荐
DB2字符串处理 字符串处理 db2 函数
字符串比较处理宏字符串比较处理宏字符串比较处理宏字符串比较处理宏
汇编字符串处理
几个字符串处理函数增强版 常用需求基本都能完成 已经编译成DLL 函数列表 兼容字符和串 void revstr char str 字符串反转 int substring char res int pos int len char substr 从pos开始取len个字符到substr中 ...
Mid Mid(string,start,length) 从string字符串的start字符开始取得length长度的字符串,如果省略第三个参数表示从start字符开始到字符串结尾的字符串 Left Left(string,length) 从string字符串的左边取得length长度...
java 常用字符串处理工具类! java 常用字符串处理工具类!
自己封装的纯C++的字符串处理函数大全,像特别好用的 字符串切分 Split函数代码均已经过测试,并有接口说明,可方便调用。
java字符串处理取出括号内的字符串 都是我自己试过可以用的j
常用字符串处理函数都列在文档里面了,但是需要使用我word 2007才能打开。
被爱可以字符串处理工具由中国被爱可以在线站长Bicyle开发,是一款字符串处理的绿色工具软件,它具有繁简体转换 、URL和HTML编码转换、字母大小写转换、邮件地址分组、半全角转换、区位码和ASCII码查询,WAP文档UTF-...
多重字符处理机制,仿照python字符串处理写的一个针对c++的字符串处理
SQL 字符串处理函数 获取指定的字符
数据库字符串处理数据库字符串处理数据库字符串处理数据库字符串处理
STL与字符串处理
C#字符串处理 C#字符串处理,轻松学习C#,轻松入门~~
常用的文本处理方法,比如过滤关键词。文本编码。去除 htmlCode 中所有的HTML标签(包括标签中的属性)。截取字符串。将Gb2312编码的字符串转换为utf-8。判断是否有非法字符。分割字符串。检测含中文字符串实际长度。...
mysql常用字符串函数、字符串处理函数大全。word文档内容中涵盖了mysql数据库字符串处理的38个函数。可完全满足日常对mysql数据库的字符处理操作。
字符串处理函数的汇总资料,供初学者参考。
字符串处理通用程序 功能说明: ①:查找 ②:删除 ③:替换 ④:插入 寄存器说明: SI:①:主串下标 ②:替换串下标 DX:保存主串下标SI AL:保存主串字符 BX:子串下标 AH:保存子串字符 DI:存储下标 标记...
c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典c#字符串处理圣盛典