• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Algorithm wanted: longest repeating substring using suffix tree

 
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic