• Post Reply Bookmark Topic Watch Topic
  • New Topic

Algorithm wanted: longest repeating substring using suffix tree  RSS feed

 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is there anyone know the algorithm of searching longest repeating substring( the substring appeared more than once in the string ) in a string? Suppose the length of the entire string is x, the computing time of this algorithm should be in O(x). Constructing a suffix tree should be the right solution. I know how to build a suffix tree, but then what? Thank you very much in advance.

Regards,
Ellen
 
Peter den Haan
author
Ranch Hand
Posts: 3252
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I assume you know how to build the suffix tree in O(N) time. The key observation is that a repeating string will give you a fork in the tree. If you define the "depth" of a node as the number of characters traversed from the root, the longest substring corresponds to the deepest fork in the tree.
You will probably find this enlightening reading.
- Peter
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hallo Peter,
I read that paper on suffix tree closely, it�s of great help. My great appreciation to you.

Best Regards,
Ellen
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!