LongestCommonSubSequence - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

StringTools

 LongestCommonSubString
 return the longest common substring of two strings
 LongestCommonSubSequence
 return the longest common subsequence of two strings

 Calling Sequence LongestCommonSubString( s1, s2 ) LongestCommonSubSequence( s1, s2 )

Parameters

 s1 - Maple string s2 - Maple string

Description

 • A substring of a string $S$ is a contiguous sequence of the characters appearing in $S$. The empty string is a substring of every string. A subsequence of a string $S$ is a sequence of characters from $S$, which may not be contiguous in $S$. Every substring of $S$ is a subsequence of $S$. For example, $"bc"$ is a substring of $"abc"$, and $"ac"$ is a subsequence of $"abc"$ which is not a substring.
 • The LongestCommonSubString( s1, s2 ) command returns from its input strings, s1 and s2, a common substring of maximum length.
 • Many common substrings of maximum length may exist. Which among the candidates is returned depends upon the suffix structure of the pair of strings, but is deterministic.
 • The LongestCommonSubSequence( s1, s2 ) command is similar, but searches for subsequences of the pair of input strings rather than substrings.
 • All of the StringTools package commands treat strings as (null-terminated) sequences of $8$-bit (ASCII) characters.  Thus, there is no support for multibyte character encodings, such as unicode encodings.

Examples

 > $\mathbf{use}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{StringTools}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{LongestCommonSubString}\left("abax","bax"\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end use}$
 ${"bax"}$ (1)
 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{LongestCommonSubString}\left("tsaxbaxyz","axcaxy"\right)$
 ${"axy"}$ (2)
 > $\mathrm{LongestCommonSubString}\left("abcde","uvabxycde"\right)$
 ${"cde"}$ (3)
 > $\mathrm{LongestCommonSubSequence}\left("abcde","uvabxycde"\right)$
 ${"abcde"}$ (4)
 > $\mathrm{LongestCommonSubString}\left("abc","xyz"\right)$
 ${""}$ (5)
 > $\mathrm{LongestCommonSubSequence}\left("abc","xyz"\right)$
 ${""}$ (6)
 > $\mathrm{seq1}≔"TAAGGTCGGCGCGCACGCTGGCGAGTATGGTGCGGAGGCCCTGGAGAGGTGAGGCTCCCTCCCCTGCTCCGACCCGGGCTCCTCGCCCGCCCGGACCCAC":$
 > $\mathrm{seq2}≔"AAGCGCCGCGCAGTCTGGGCTCCGCACACTTCTGGTCCAGTCCGACTGAGAAGGAACCACCATGGTGCTGTCTCCCGCTGACAAGACCAACATCAAGACTGCCTGGGAAAAGATCGGCAGCCACGGTGGCGAGTATGGCGCCGAGGCCGT":$
 > $\mathrm{LongestCommonSubString}\left(\mathrm{seq1},\mathrm{seq2}\right)$
 ${"TGGCGAGTATGG"}$ (7)
 > $\mathrm{LongestCommonSubSequence}\left(\mathrm{seq1},\mathrm{seq2}\right)$
 ${"AAGGCCGCGCAGCTGGCGATTGGTCAGCCCTGGAAGGTGGGCTCTCCCCTGCTCGACCCGGGTCCGCCCGCGGACCCA"}$ (8)

 See Also