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

把酒泯恩仇

浏览: 27175 次
性别:
来自: 广州

最近访客更多访客>>

nic.z

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (14)

社区版块

存档分类

算法 C++

请查看原文：

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 &amp;&amp; q &amp;&amp; *p == *q){
		size++;
		p++;
		q++;
	}
	return size;
}

int maxlen = -1;
int current_size = -1;
for(int i = 0; i &lt; n; i++){
	for(int j = i + 1; j &lt; n; j++){
                if( (current_size = cmp_str(&amp;input_string[i], &amp;input_string[j]) ) &gt; 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++]       = &amp;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 &lt; max_word - 1; i++) { 		if( (current_size = cmp_str(word[i], word[i+1])) &gt; max_len ) {
			max_len = current_size;
			index   = i;
		}
	}