# Which algorithm to use to find all common substring (LCS case) with really big strings

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).

• 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.) 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. Nov 3 '14 at 10:26