1

How can i find LCS (longest common substring) among two or more strings using trie ?

I have an idea like this - suppose my first string is "abbcabdd". then i will first insert "abbcabdd" in trie ,then "bbcabdd", then "bcabdd" .... , then "d" and repeat this process for every string .

Then calculate the longest substring by traversing the trie.

but i think it is not efficient. Is there any other improved method ?

palatok
  • 1,022
  • 5
  • 20
  • 30

1 Answers1

4

What you are describing is exactly a suffix tree - Use an algorithm optimized to generate a suffix tree, and you will get your efficiency increased!

Note that there is an algorithm for building a suffix tree in O(n) (assuming a constant alphabet, of course).

amit
  • 175,853
  • 27
  • 231
  • 333
  • thanks. yes i'm describing the suffix tree. my suffix tree implementation is fast enough but i'm worried about my algorithm of inserting n strings for every string where n= stringLength. – palatok Oct 16 '12 at 22:49
  • @palatok: You can use the suffix tree builder algorithm - it will yield the same result, and is already researched and analyzed, no need to reinvent the wheel here. Creating a suffix tree is `O(n)`. – amit Oct 16 '12 at 22:50