2
$\begingroup$

I'm currently thinking about the following problem:

Given two strings $S,T$ over an alphabet $\Sigma$, return back a list $L$ of common substrings described by their length and positions within them.

I am interested only in maximal substrings as to not have redundancy. Meaning that for a substring of length $l$ with starting positions $i$ in $S$ and $j$ in $T$, $S_{i–1} \neq T_{j–1}$ and $S_{i+l} \neq T_{j+l}$.

I am looking for a practical $O(|S|+|T|)$ solution. I wanted a bottom-up approach using hashing (a rolling hash?) that will build up the substrings as it runs. The Reputer algorithm advised to me in my previous post which is now linked gives a solution using suffix trees. I was wondering if any similar approaches have been made using hashing and if any papers exist describing them.

$\endgroup$
  • $\begingroup$ Exactly what is a "matching substrings"? $\endgroup$ – Jukka Suomela Oct 5 '11 at 20:41
  • 3
    $\begingroup$ And how is this related to cstheory.stackexchange.com/questions/8361/… ? $\endgroup$ – Jukka Suomela Oct 5 '11 at 20:42
  • $\begingroup$ @JukkaSuomela sorry, by matching substrings I mean common substrings. I had trouble in that post conveying what I wanted and I incorrectly tagged the question at first so I was explaining the incorrect tag and poorly describing the problem over and over rather than getting to really discuss it. Trying again. $\endgroup$ – mcorley Oct 6 '11 at 1:38
  • $\begingroup$ Once again, you cannot have an $O(|S|+|T|)$ algorithm, as the size of the output can be quadratic. For example, if your input strings are ABABABAB....AB and ACACACAC...AC, both of them of length $2n$, you can find $n^2$ maximal common substrings of length 1. So if you think there is a linear-time algorithm, I guess something is missing in your problem formulation. $\endgroup$ – Jukka Suomela Oct 6 '11 at 7:26
  • $\begingroup$ The dictionary of maximal repeated substrings is linear in size in the sense that there are at most a linear number of words in the dictionary, each of which can be represented by a pair of integers (it's a subset of the nodes of the suffix tree of the two strings concatenated). What is not linear is the list of all locations of where those repeats occur. $\endgroup$ – Raphael Oct 6 '11 at 9:30
2
$\begingroup$

The answer is no. To find the full dictionary of maximal repeated substrings in linear time is a hard problem if no one has ever introduced you to a suffix tree or equivalent. However, if you don't like using suffix trees, you can achieve much the same result using suffix arrays which can be a little easier to handle.

EDIT: Well... actually this isn't strictly a full answer if you are happy with a slightly super-linear time solution. You can in that case use the rather lovely result from 1972 "Rapid identification of repeated patterns in strings, trees and arrays" by Karp, Miller and Rosenberg.

Can I ask, what is your motivation? You use the word practical but there is nothing impractical about the suffix tree based methods, unless your data is too large to fit in RAM. In which case the problem becomes interesting again.

$\endgroup$
  • $\begingroup$ The suffix tree/suffix array solution is what I will probably end up using it seems. Thanks for the referenced paper I will check it out today. $\endgroup$ – mcorley Oct 6 '11 at 16:20
  • $\begingroup$ My motivation is in designing a new file difference algorithm. The first step is to locate regions of the files that are unchanged. Doing so I would have partitioned the files into two kinds of blocks; blocks that exists in both files, blocks that differ in some way. I am therefore not actually interested in all common substrings, but enough to uniformly partition the files in such a way. Does this make sense? $\endgroup$ – mcorley Oct 6 '11 at 16:35
  • $\begingroup$ My pleasure. If you find it useful, please feel free to upvote. $\endgroup$ – Raphael Oct 6 '11 at 18:21
  • $\begingroup$ @RaphaelClifford: Voting up requires rep points ≥ 15, while the current rep point of the asker is 6. $\endgroup$ – Tsuyoshi Ito Oct 6 '11 at 18:33
  • $\begingroup$ @RaphaelClifford Your post definitely deserves an upvote but as the previous comment mentions my reputation is not quite there yet to do so. I hope a thanks will do for now! $\endgroup$ – mcorley Oct 6 '11 at 20:39
0
$\begingroup$

I was looking at a LZ77 based algorithm that also provides a solution to this problem and wanted to share. In particular, this paper. Their algorithm also makes use of the fingerprinting method from karp and rabin's string search algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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