1、 查找一個字符串中最長的重復子串；
2、 查找一個字符串中重復最多的子串；
查找“重復子串最長的”和“子串出現(xiàn)次數(shù)最多的”解決方案相似：
首先、生成一個指針數(shù)組，數(shù)組的成員依次指向字符串中每一個的字符地址，如
String: “banana”
那么指針數(shù)組分別代表字串：
banana
anana
nana
ana
na
a
之后按指針數(shù)組指向的字符串值，對數(shù)組進行排序，排序結果如下：
a[0]: a
a[1]: ana
a[2]: anana
a[3]: banana
a[4]: na
a[5]: nana
有個這個數(shù)組，統(tǒng)計“重復的最長子串”和“重復次數(shù)最多子串”就非常容易了。
“重復的最長子串”代碼如下：
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
胡滿超 閱讀(548)
評論(1) 編輯 收藏 引用