<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-06T16:20:37.020Z
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.
mcorley
CC BY-SA 3.0
2011-10-06T16:35:22.647Z
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?
mcorley
CC BY-SA 3.0
2011-10-06T18:21:10.043Z
My pleasure. If you find it useful, please feel free to upvote.
Simd
CC BY-SA 3.0
2011-10-06T18:33:36.687Z
@RaphaelClifford: [Voting up](http://cstheory.stackexchange.com/privileges/vote-up) requires rep points ≥ 15, while the current rep point of the asker is 6.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-06T20:39:50.167Z
@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!
mcorley
CC BY-SA 3.0
2011-10-06T20:43:47.963Z
The paper you referenced more accurately states my problem: Given strings $S$ and $T$ over $\Sigma$ find all occurrences of $S$ in $T$. I am currently browsing papers for further analysis of this problem and alternate solutions. If this helps at all linking me to any other papers you know of, link away!
mcorley
CC BY-SA 3.0
2011-10-07T13:52:23.670Z
@mcorley: the Wikipedia page on string search compares several algorithms, and has multiple links: http://en.m.wikipedia.org/wiki/String_searching_algorithm
Aaron Sterling
CC BY-SA 3.0
2011-10-06T09:29:12.267Z
2011-10-06T09:52:03.213Z
2011-10-06T09:52:03.213Z
Simd
<p>I was looking at a <a href="http://en.wikipedia.org/wiki/LZ77_and_LZ78" rel="nofollow">LZ77</a> based algorithm that also provides a solution to this problem and wanted to share. In particular, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8470" rel="nofollow">this paper</a>. Their algorithm also makes use of the fingerprinting method from karp and rabin's string search algorithm.</p>

CC BY-SA 3.0
2011-10-10T02:18:10.740Z
2011-10-10T02:18:10.740Z
mcorley
<p>I'm currently thinking about the following problem:</p>

<p>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.</p>

<p>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}$.</p>

<p>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 <a href="http://bibiserv.techfak.uni-bielefeld.de/reputer/" rel="nofollow noreferrer">Reputer algorithm</a> advised to me in <a href="https://cstheory.stackexchange.com/q/8361/">my previous post</a> 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.</p>

CC BY-SA 3.0
2011-10-05T20:41:15.790Z
Exactly what is a "matching substrings"?
Jukka Suomela
CC BY-SA 3.0
2011-10-05T20:42:45.507Z
And how is this related to http://cstheory.stackexchange.com/questions/8361/algorithm-find-the-first-k-longest-substrings-between-two-similar-strings ?
Jukka Suomela
CC BY-SA 3.0
2011-10-06T01:38:47.493Z
@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.
mcorley
CC BY-SA 3.0
2011-10-06T07:26:57.567Z
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.
Jukka Suomela
CC BY-SA 3.0
2011-10-06T09:30:30.457Z
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.
Simd
<ds.algorithms><string-matching>
Matching substrings within two strings
mcorley
# Matching substrings within two strings

(Asked by: username_0 on 2011-10-05)

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](http://bibiserv.techfak.uni-bielefeld.de/reputer/) advised to me in [my previous post](https://cstheory.stackexchange.com/q/8361/) 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.

**Tags:** ds.algorithms, string-matching

> **Comments:**
> **username_1**: Exactly what is a "matching substrings"?  
> **username_1**: And how is this related to http://cstheory.stackexchange.com/questions/8361/algorithm-find-the-first-k-longest-substrings-between-two-similar-strings ?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-10-06. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_2**: My pleasure. If you find it useful, please feel free to upvote.  
> **username_3**: @RaphaelClifford: [Voting up](http://cstheory.stackexchange.com/privileges/vote-up) requires rep points ≥ 15, while the current rep point of the asker is 6.  
> **username_0**: @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!  
> **username_0**: The paper you referenced more accurately states my problem: Given strings $S$ and $T$ over $\Sigma$ find all occurrences of $S$ in $T$. I am currently browsing papers for further analysis of this problem and alternate solutions. If this helps at all linking me to any other papers you know of, link away!  
> **username_4**: @username_0: the Wikipedia page on string search compares several algorithms, and has multiple links: http://en.m.wikipedia.org/wiki/String_searching_algorithm  

---

### Answer by username_0 on 2011-10-10. Score: 0

I was looking at a [LZ77](http://en.wikipedia.org/wiki/LZ77_and_LZ78) based algorithm that also provides a solution to this problem and wanted to share. In particular, [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8470). Their algorithm also makes use of the fingerprinting method from karp and rabin's string search algorithm.


---

