Longest common substring problem

Longest common substring problem

The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. It should not be confused with the longest common subsequence problem. (For an explanation of the difference between a substring and a subsequence, see substring).

Example

The longest common substrings of the strings "ABAB", "BABA" and "ABBA" are the strings "AB" and "BA" of length 2. Other common substrings are "A", "B" and the empty string "".

ABAB
|
BABA
ABBA

Problem definition

Given two strings, S of length m and T of length n, find the longest strings which are a substrings of both S and T.

A generalisation is the k-common substring problem. Given the set of strings S = {S_1, ..., S_K}, where |S_i|=n_i and Σn_i = N. Find for each 2 ≤ k ≤ K, the longest strings which occur as substrings of at least k strings.

Algorithms

You can find the lengths and starting positions of the longest common substrings of S and T in Theta(n+m) with the help of a generalised suffix tree. Finding them by dynamic programming costs Theta(nm). The solutions to the generalised problem take Theta(n_1 + ... + n_K) and Theta(n_1·...·n_K) time.

uffix tree

You can find the longest common substrings of a set of strings by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which has leaf nodes from all the strings in the subtree below it. In the figure on the right you see the suffix tree for the strings "ABAB", "BABA" and "ABBA", padded with unique string terminators, to become "ABAB$0", "BABA$1" and "ABBA$2". The nodes representing "A", "B", "AB" and "BA" all have descendant leaves from all of the strings, numbered 0, 1 and 2.

Building the suffix tree takes Theta(n) time (if the size of the alphabet is constant). If you traverse the tree bottom up, and maintain a bit vector telling which strings are seen below each node, you can solve the k-common substring problem in Theta(NK) time. If you prepare your suffix tree for constant time lowest common ancestor retrieval, you can solve it in Theta(N) time.cite book | last = Gusfield | first = Dan | origyear = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | id = ISBN 0-521-58519-8]

Dynamic programming

You first find the longest common suffix for all pairs of prefixes of the strings. The longest common suffix is

mathit{LCSuff}(S_{1..p}, T_{1..q}) = egin{cases} mathit{LCSuff}(S_{1..p-1}, T_{1..q-1}) + 1 & mathrm{if } ; S [p] = T [q] \ 0 & mathrm{otherwise}end{cases}

For the example strings "ABAB" and "BABA":

The maximal of these longest common suffixes of possible prefixes must be the longest common substrings of "S" and "T". These are shown on diagonals, in red, in the table.

mathit{LCSubstr}(S, T) = max_{1 leq i leq m, 1 leq j leq n} mathit{LCSuff}(S_{1..i}, T_{1..j}) ;

This can be extended to more than two strings by adding more dimensions to the table.

Pseudocode

The following pseudocode finds the set of longest common substrings between two strings with dynamic programming:

function LCSubstr(S [1..m] , T [1..n] ) L := array(0..m, 0..n) z := 0 ret := {} for i := 1..m for j := 1..n if S [i] = T [j] if i = 1 or j = 1 L [i,j] := 1 else L [i,j] := L [i-1,j-1] + 1 if L [i,j] > z z := L [i,j] ret := {} if L [i,j] = z ret := ret ∪ {S [i-z+1..i] } return ret

This algorithm runs in O(m n) time. The variable z is used to hold the length of the longest common substring found so far. The set ret is used to hold the set of strings which are of length z

The following tricks can be used to reduce the memory usage of an implementation:
* Keep only the last and current row of the DP table to save memory (O(min(m, n)) instead of O(m n))
* Store only non-zero values in the rows. You can do this by using hash tables instead of arrays. This is useful for large alphabets.

References

External links

* [http://nist.gov/dads/HTML/longestCommonSubstring.html Dictionary of Algorithms and Data Structures: longest common substring]
* [http://search.cpan.org/perldoc?String::LCSS_XS Perl/XS implementation of the dynamic programming algorithm]
* [http://search.cpan.org/perldoc?Tree::Suffix Perl/XS implementation of the suffix tree algorithm]
* [http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring Dynamic programming implementations in various languages on wikibooks]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Longest common subsequence problem — Not to be confused with longest common substring problem. The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). Note that subsequence is different from a… …   Wikipedia

  • Substring — A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved. In this context, the terms string and sequence have the same meaning. Subsequence : Main article… …   Wikipedia

  • Suffix tree — In computer science, a suffix tree (also called suffix trie, PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Subsequence — In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. Formally, suppose that X is a set… …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”