1、 查找一个字符串中最长的重复子串；
2、 查找一个字符串中重复最多的子串；
查找“重复子串最长的”和“子串出现次数最多的”解决方案相似：
首先、生成一个指针数组，数组的成员依次指向字符串中每一个的字符地址，如
String: “banana”
那么指针数组分别代表字串：
banana
anana
nana
ana
na
a
之后按指针数组指向的字符串值，对数组进行排序，排序结果如下：
a[0]: a
a[1]: ana
a[2]: anana
a[3]: banana
a[4]: na
a[5]: nana
有个这个数组，统计“重复的最长子串”和“重复次数最多子串”就非常容易了。
“重复的最长子串”代码如下：
1 int comlen(char *p, char *q)
2 {
3 i = 0
4 while *p && (*p++ == *q++)
5 i++
6 return i
7 }
8
9 maxlen = -1
10 for i = [0, n)
11 for j = (i, n)
12 if (thislen = comlen(&c[i], &c[j])) > maxlen
13 maxlen = thislen
14 maxi = i maxj = j
这个方法出自《编程珠玑》。
posted on 2009-12-16 14:07
胡满超 阅读(544)
评论(1) 编辑 收藏 引用