3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you please add a reference to the original problem? 1) Credit should be attributed. 2) The original problem is probably stated clearer. 3) A reference is apt to motivate people. 4) A reference may save readers who look for related materials lots of time. $\endgroup$ – Apass.Jack May 12 at 17:55
  • $\begingroup$ There is no original definition, as this is an actual problem I'm currently facing in software dev. I'd be happy to clarify. Currently, I didn't find any formal definition.. that would've helped me too :) $\endgroup$ – Fimka May 13 at 8:17
  • $\begingroup$ If it comes from yourself, can you describe the background briefly? $\endgroup$ – Apass.Jack May 13 at 13:39
  • $\begingroup$ program to find recurring substrings between logging messages. $\endgroup$ – Fimka May 13 at 15:01
  • $\begingroup$ My bad. No, since they aren't longest common substring ( correct answer is "cde" and "cd".). Thanks, I've updated the description. $\endgroup$ – Fimka May 13 at 15:08
1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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
$\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.