字符串处理新思维啊【不得不看】_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 字符串处理新思维啊【不得不看】

字符串处理新思维啊【不得不看】

 2013/8/14 23:43:48  把酒泯恩仇  程序员俱乐部  我要评论(0)
  • 摘要:请查看原文:http://www.ibaiyang.org/2012/03/25/repeat-substring/最近在看《编程珠玑》,很多人说,应该看看这本神书,于是跟风,我也买了一本,不过才拿到这本书的时候,觉得也是一般,前面几章的例题很是一般,而且感觉作者分析的东西自己不是很实用,比如二分搜索就讲了2,3章,虽然作者对二份搜索的理解与实现,吹毛求疵,但是整体上来说,觉得没有意思,没有给人一张豁然开朗的感觉,在看到第二章时,讲到了变位词的算法,才令人痴迷,于是我疯狂的继续看下去
  • 标签:字符串

?

请查看原文:

http://www.ibaiyang.org/2012/03/25/repeat-substring/

最近在看《编程珠玑》,很多人说,应该看看这本神书,于是跟风,我也买了一本,不过才拿到这本书的时候,觉得也是一般,前面几章的例题很是一般,而且感觉作者分析的东西自己不是很实用,比如二分搜索就讲了2,3章,虽然作者对二份搜索的理解与实现,吹毛求疵,但是整体上来说,觉得没有意思,没有给人一张豁然开朗的感觉,在看到第二章时,讲到了变位词算法,才令人痴迷,于是我疯狂的继续看下去,今天看到了重复字符串的实现方式,我高兴的立刻想发篇博文,来证实它多么的奇妙。

求一个字符串的最长重复字符串,就是在一个长字符串中,找出有重复的字符串,且其长度最长,我感觉这个题的引申意义也很大,特别在如今搜索引擎的时代。例如banana的最长字符串是ana,tian xian的最长字符串是ian。好了,看看是怎么实现的吧。

class="wp-code-highlight prettyprint">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";

这些就成为“后缀数组”,如果你能理解hashu.html" target="_blank">二叉树,我相信这个也能理解吧。

如果某个长字符串在数组中出现二次,那么它将出现在二个不同的后缀中,因此我们队数组排序以寻找相同的后缀。

如对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/

如果您想转载本博客,请注明出处

如果您对本文有意见或者建议,欢迎留言

?

发表评论
用户名: 匿名