CODEWITHSUNDEEP
algorithmsortingdictionarydata-structuresternary-search-tree
Proud
Proud

Reputation: 39

Finding longest common prefix in a ternary search tree

I implement a ternary search tree for a 20000 words.I want to know an algorithm to find a longest common prefix(prefix that is shared by at least 2 words)? Is there anyway to find a Longest Common Prefix in a tree?(without ternary search tree)

Upvotes: 1

Views: 451

Answers (1)

Mark
Mark

Reputation: 1100

There is a very easy solution and it is linear complexity, You know that Rabin-Karp is a string matching algorithm that uses hashing to do that. The ideea is to create a hash table. You go through all the words and at each length 1, 2, .. len( word ) you put the key( the hash value for that substring ) in the table , and when you already have that key in the table that means you have 2 words ( at least ) with that hash value. Then you only need to find the longest index that has that property.

Upvotes: 2

Related Questions