mobit's blog

LCS longest ...
By mobit, 12 years ago, In English

Hi , I have been thinking a lot but I haven't had any good idea about this , so I want your help : We are given an integer N and N strings , how could we find the longest common substring of them and the length of longest common substring of them ?

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

Build a generalized suffix array. Then for each inclusion-minimal window that contains a suffix from all the N strings, an answer candidate is the LCP of all of them. You can use two pointers and a set data structure to find all such inclusion-minimal windows. The runtime is expected linear if you use hash tables and a fast suffix array construction.

→ Reply