随笔 - 89  文章 - 118  trackbacks - 0
<2009年12月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

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++ == *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 胡满超 阅读(543) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 字符串相关算法介绍2,3 2010-08-13 09:54 miselanse
对指针数组排完序后,不必再用O(n^3)的算法找最长重复字串了,只需要O(n^2)的算法与相邻元素比较即可,如下:
for (i = 0; i<n; i++)
{
if ((thislen=comlen(a[i], a[i+1])) > maxlen)
{
maxlen=thislen;
maxi = i;
}
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理