Longest common substring many strings to one

Question

I'd like to find longest common substring (occurrences, start index) between one string and many others.

For example

• source string - "abcdefghijklmncdop"

• other strings - ["cd", "ghi", "mn", "zw", "cdewxyz"].

• Expected result -(original string, substring, index in source string) = [(cd,cd,2),(cd,cd,14),(ghi,ghi,7 ),...(cdewxyz, cde, 3]

I could create suffix array from the source string and search all possible substring occurrences sequentially - but it doesn't seem that efficient. The other strings array might be very large, so creating joint arrays with special delimiter is not considered.

I also thought on creating suffix tree, but I there are many source strings soe space complexity might become an issue.

Answer 1

Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to the suffix tree.

Here's pseudocode that finds $M$ - location in the suffix tree (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$:

M := C := ST.root

for i := 1..|T| do
  while C.canNotExtendWith(T[i]) do
    C := C.contract()

  C := C.extendWith(T[i])

  if C.length > M.length then
    M := C

Here:

1. ST.root is the suffix tree root
2. C.canNotExtendWith(x) returns true if you can't follow given letter $x$ from location $C$
3. If $C$ is a location of string $U$ in the tree, then C.extendWith(x) returns location of string $Ux$
4. If $C$ is a location of string $xU$, then C.contract() returns location of $U$ (i.e. follows the suffix link)
5. If $C$ is a location of string $U$, then C.length is $|U|$

Both correctness and $\mathcal{O}(|T|)$ time complexity follow from the Ukkonen's algorithm.

Hand-wavy explanation of the algorithm correctness:

1. If you can't extend the substring with single letter, there's no point in trying to extend it further
2. If you've already found a good candidate substring, there's no point in contracting it

Answer 2

I suspect there's nothing better than the following iterative algorithm: for each $i$ in $1,2,\dots,n$, find the longest common substring between $S$ and $T_i$ (where $S$ is the one string and $T_1,\dots,T_n$ are the other strings).

If you only want to find a longest common substring between $S$ and $T_i$, this can be done in linear time, i.e., $O(|S|+|T_i|)$ time, where $|S|$ is the length of the string $S$ and $|T_i|$ is the length of the string $T_i$. There are many ways to do it in linear time; for instance, you can concatenate them with a delimiter and then use a suffix tree or a suffix array. If you want to find all common substrings of that length, it takes $O(|S|+|T_i|+m)$ time, where $m$ is the number of such substrings, if you're satisfied with printing out just the indices where these substrings exist; if you also want to also print out the strings themselves, then the running time is $O(|S|+|T_i|+mk)$, where $k$ is the length of the longest common substring.

If you want to do this between $S$ and each of the $T_i$'s, sum this up over all the $i$'s.

The space complexity is $O(|S|+\max_i |T_i|)$, since you can throw away the data structure for $S,T_i$ after you're finished with $T_i$ and before you start with $S,T_{i+1}$.

Answer 3

The answer greatly depends on practical details. One possible algorithm is the following:

1. Build SA from the source string
2. Sort other strings (it will be O(N + TotalLength) using radix sort) into OA
3. Split one of two arrays (SA or OA) into two halves and find the corresponding point in the opposite array
4. Repeat the last step recursively, until you find position pair in SA for each string of OA