Longest common substring

The strings "BADANAT" and "CANADAS" share the maximal-length substrings "ADA" and "ANA".

The picture shows two strings where the problem has multiple solutions. Although the substring occurrences always overlap, no longer common substring can be obtained by "uniting" them.

The strings "ABABC", "BABCA" and "ABCBA" have only one longest common substring, viz. "ABC" of length 3. Other common substrings are "A", "AB", "B", "BA", "BC" and "C".

  ABABC
    |||
   BABCA
    |||
    ABCBA

Given two strings, ${\displaystyle S}$ of length ${\displaystyle m}$ and ${\displaystyle T}$ of length ${\displaystyle n}$, find a longest string which is substring of both ${\displaystyle S}$ and ${\displaystyle T}$.

A generalization is the k-common substring problem. Given the set of strings ${\displaystyle S=\{S_{1},...,S_{K}\}}$, where ${\displaystyle |S_{i}|=n_{i}}$ and ${\displaystyle \Sigma n_{i}=N}$. Find for each ${\displaystyle 2\leq k\leq K}$, a longest string which occurs as substring of at least ${\displaystyle k}$ strings.

One can find the lengths and starting positions of the longest common substrings of ${\displaystyle S}$ and ${\displaystyle T}$ in ${\displaystyle \Theta }$${\displaystyle (n+m)}$ time with the help of a generalized suffix tree. A faster algorithm can be achieved in the word RAM model of computation if the size ${\displaystyle \sigma }$ of the input alphabet is in ${\displaystyle 2^{o({\sqrt {\log(n+m)}})}}$. In particular, this algorithm runs in ${\displaystyle O((n+m)\log \sigma /{\sqrt {\log(n+m)}})}$ time using ${\displaystyle O((n+m)\log \sigma /\log(n+m))}$ space.[1] Solving the problem by dynamic programming costs ${\displaystyle \Theta (nm)}$. The solutions to the generalized problem take ${\displaystyle \Theta (n_{1}+...+n_{K})}$ space and ${\displaystyle \Theta (n_{1}}$·...·${\displaystyle n_{K})}$ time with dynamic programming and take ${\displaystyle \Theta ((n_{1}+...+n_{K})*K)}$ time with a generalized suffix tree.

Suffix tree

Generalized suffix tree for the strings "ABAB", "BABA" and "ABBA", numbered 0, 1 and 2.

The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it. The figure on the right is 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 ${\displaystyle \Theta (N)}$ time (if the size of the alphabet is constant). If the tree is traversed from the bottom up with a bit vector telling which strings are seen below each node, the k-common substring problem can be solved in ${\displaystyle \Theta (NK)}$ time. If the suffix tree is prepared for constant time lowest common ancestor retrieval, it can be solved in ${\displaystyle \Theta (N)}$ time.[2]

function LongestCommonSubstring(S[1..r], T[1..n])
    L := array(1..r, 1..n)
    z := 0
    ret := {}

    for i := 1..r
        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 := {S[i − z + 1..i]}
                else if L[i, j] = z
                    ret := ret ∪ {S[i − z + 1..i]}
            else
                L[i, j] := 0
    return ret

• Longest palindromic substring
• n-gram, all the possible substrings of length n that are contained in a string

The Wikibook Algorithm implementation has a page on the topic of: Longest common substring

• Dictionary of Algorithms and Data Structures: longest common substring
• Perl/XS implementation of the dynamic programming algorithm
• Perl/XS implementation of the suffix tree algorithm
• Dynamic programming implementations in various languages on wikibooks
• working AS3 implementation of the dynamic programming algorithm
• Suffix Tree based C implementation of Longest common substring for two strings