Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I am trying to use suffix trees to compare string sequences. I have found implementations/theory for the longest common sub string problem using suffix trees. However, What i am looking for is a discussion of the related problem - "all common substrings". Specifically, I have a problem in which i need to first find the longest common substring, then find the next longest common substring that does not include the already found lcs indices, and so on until a minimum length. Is this problem solvable by constructing the Generalized suffix tree (GST) only once for the two sequences. I know it can be solved by repeatedly constructing a GST after every iteration of finding and removing the LCS. But, I am wondering if i am missing a neat trick where in the GST is constructed only once.

share|improve this question
    
It's an interesting question. The problem is that if we have $S=\alpha\beta\gamma$ and we have found that $\beta$ is the LCS w.r.t. $T$, we can't easily "remove" $\beta$ from suffix tree (or suffix array, whatever). We'd like to have something like $S' = \alpha\$\gamma$ after first step, right? –  Dmytro Korduban Feb 29 '12 at 10:05

4 Answers 4

Yes, suffix trees can be used to find all common substrings. I would say to use a suffix array instead, but if you already have a suffix tree, building a suffix array from a suffix tree takes linear time by DFS. So the rest of my answer will assume we are working with a suffix array.

Given a text $S = s_1 , ..., s_n$, a suffix array for $S$ is an array of integers of range $0$ to $n$ specifying the lexicographic ordering of the $n+1$ suffixes of the string $S$\$

We want to couple the suffix array with the $LCPs$, the longest common prefixes. We can construct the array of $LCPs$ in linear time as mentioned in the paper by Kasai et al. Suffix arrays and their lcp arrays line up together in a way that given an index into the lcp array say $lcp[k]$ where $k$ is the index number, then $sa[k]$ will be the start of one instance of the common substring and $sa[k-1]$ will be the start index of the second instance. The length is of course the value in the lcp array.

share|improve this answer

I have an idea that might work. We start with a generalized suffix tree for sequences $S$ and $T$. Each internal node with suffixes of both $S$ and $T$ in its subtree corresponds to some common substring of the sequences. Let us call such nodes non-trivial. The common substring is maximal, if the corresponding node has no non-trivial children. If node $v$ is non-trivial, we store the largest string-depth of a non-trivial node in its subtree as $lcs(v)$. If $r$ is the root, then $lcs(r)$ is the length of the longest common substring of $S$ and $T$.

Updating the tree after deleting a substring from one of the sequences should not be too hard. We first delete the leaves corresponding to the deleted suffixes, updating their ancestors when required. Then we start processing the suffixes preceding the deleted substring. Let $v$ be the lowest non-trivial ancestor of the current leaf. If the length of the suffix is $k$ (we are $k$ steps from the deletion) and $k < lcs(v)$, we have to move the suffix to its proper position in the tree, updating the ancestors when required. If $k \ge lcs(v)$, we are done, as we are not interested in subtrees with trivial roots.

The overall algorithm repeatedly finds the longest common substring of $S$ and $T$ and deletes one of its occurrences from both sequences, as long as the length of the LCS is large enough.

There are some technicalities, but the general idea should work.

share|improve this answer

Start with the concatenated text S$T, where $ occurs nowhere in * or T. Construct a suffix tree/array from this text. It's easy now to traverse this suffix data structure to collect all right maximal repeats. By examining the left context, filter out the non-left maximal repeats. This leftward filtering might be implemented using the Burrows-Wheeler table as in Abouelhoda et al, though I don't believe that this is necessary. Repeats occuring only in S or only in T should olso be eliminated at this point. Repeats that haven't been eliminated are then put on a priority queue, with priority defined by length. After the traversal, as recorded repeats are removed from the priority, the final filtering (for substring containment) can be carried out. Given the use of maximal phrases, however, I suspect that very little of this filtering would be necessary.

This algorithm is my own invention. I would not classify it as very clever, but it ought to work.

share|improve this answer

A really simple solution: Build a suffix tree for the first string, $S$, and annotate all nodes with $s$. Then insert all suffixes of the second string, $T$. Annotate nodes you pass through or create with $t$. The path label for any node that is annotated with both $s$ and $t$ is a substring of both $S$ and $T$. (See, for example, these lecture notes a quick web search turned up.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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