c****r
发帖数: 576 | 1 听说这里讨论过这个问题，翻了十几页没找到。恳请指点。
【 以下文字转载自 Computation 讨论区 】
发信人: jzxu (自然), 信区: Computation
标 题: Re: 问一个简单问题的算法
发信站: BBS 未名空间站 (Sat Sep 1 10:25:18 2007), 转信
这个在programming版曾经讨论过，你到哪里去找找。 |
I**********s
发帖数: 441 | 2 可以试一下 Suffix tree.
"Algorithms on Strings, Trees, and Sequences" by Dan Gusfield
(ISBN 0-521-58519-8, QA76.9.A43387 1997) 详细介绍了string的相关算法.
你的问题看来比较类似书中第7.12节:
Finding all maximal repetivive structures in linear time. |
l*******o
发帖数: 12469 | 3
好像suffix tree是解决这个问题的最好方法？
【在 I**********s 的大作中提到】
: 可以试一下 Suffix tree.
: "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield
: (ISBN 0-521-58519-8, QA76.9.A43387 1997) 详细介绍了string的相关算法.
: 你的问题看来比较类似书中第7.12节:
: Finding all maximal repetivive structures in linear time.
|
c****r
发帖数: 576 | 4 多谢！在google books里面找到了这本书！
【在 I**********s 的大作中提到】
: 可以试一下 Suffix tree.
: "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield
: (ISBN 0-521-58519-8, QA76.9.A43387 1997) 详细介绍了string的相关算法.
: 你的问题看来比较类似书中第7.12节:
: Finding all maximal repetivive structures in linear time.
|
s****u
发帖数: 118 | 5 suffix tree我觉得很复杂，要简单一点的话可以试试suffix array
理论复杂度会高一点
【在 l*******o 的大作中提到】
:
: 好像suffix tree是解决这个问题的最好方法？
|
f*l
发帖数: 161 | 6 programming pearls上讲过，suffix array，然后用quicksort排序。
【在 s****u 的大作中提到】
: suffix tree我觉得很复杂，要简单一点的话可以试试suffix array
: 理论复杂度会高一点
|
l*******o
发帖数: 12469 | 7
suffix tree还是比较好理解的吧，suffix array的理论好像却是复杂点。
【在 s****u 的大作中提到】
: suffix tree我觉得很复杂，要简单一点的话可以试试suffix array
: 理论复杂度会高一点
|
