1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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.) $\endgroup$
    – David Richerby
    Commented Oct 29, 2014 at 9:11
  • $\begingroup$ Define "best". There are many possible metrics. $\endgroup$
    – Raphael
    Commented Oct 29, 2014 at 10:19
  • $\begingroup$ 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. $\endgroup$
    – Ivan
    Commented Oct 29, 2014 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – reinierpost
    Commented Nov 3, 2014 at 10:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – David Richerby
    Commented Oct 30, 2014 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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