I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other long strings.

A simplified example

$S_0$ = ABBCADGGHEEASSSCC

$S_1$ = ABDCADGGHMEASSSAC

the LCS = CADGGH (6 chars) and other long strings with 5 chars are CADGG, ADGGH and EASSS.

Which is the fastest algorithm to get all substrings with its length? (list all substrigs and legths) And in my case (very big byte substrings) which is the fastest LCS algorithm? (only get longest common substrings).

NOTE: In particular I don't have any space limit now, but this algorithm may be implemented in a mobile device in a future and is possible to have a very limited RAM/disk space (but always, at least, I have the same disk space available as the sum of file lengths).

  • 2
    Welcome to Computer Science Stack Exchange! What did you try? Where did you look for answers before asking here? (You did look somewhere, right? It would be helpful for people to know where you looked so they don't need to look for the answer there, too.) – David Richerby Oct 29 '14 at 9:11
  • Define "best". There are many possible metrics. – Raphael Oct 29 '14 at 10:19
  • Sorry, @Raphael it's true what you say, I'm asking for the "fastest" algorithm. I've used before LCS algorithms in other context (this implementation: ics.uci.edu/~eppstein/161/960229.html), but never with strings with milions of characters. This paper is really old but functional in relative short strings. I'm looking for a solution that don't takes more than a minute to resolve the problem, if exist. – Ivan Oct 29 '14 at 14:33
  • You are probably going to be able to optimize a lot by looking at the kinds of strings you typically encounter. Their distribution is probably heavily skewed in some direction. – reinierpost Nov 3 '14 at 10:26

I came across this problem before. I compressed the strings and applied dynamic programming on the compressed strings.

For compression techniques, I followed the methods described in this paper: http://pdf.aminer.org/000/145/966/data_compression_using_long_common_strings.pdf

The speed was decent. But, it consumed some space though.

  • Welcome to Computer Science Stack Exchange! Some more detail would be very helpful. What is "decent" speed? How much is "some space"? Could you at least summarize the contents of the paper and give a proper citation to it? Links often disappear and, without a working link, your answer has almost nothing in it. Thanks! – David Richerby Oct 30 '14 at 0:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.