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
  • 982
  • 4
  • 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
  • 172,148
  • 26
  • 225
  • 324
  • 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