StringTools - Maple Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : String Homology Routines : StringTools/LongestCommonSubString

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.

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)