Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes forum!
  • 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
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

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
 
Can't .... do .... plaid .... So I did this tiny ad instead:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic