StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : Combinatorics on Words : StringTools/Border

StringTools

 Border
 compute the border of a string
 BorderLength
 compute the length of the border of a string
 BorderArray
 compute a list of border lengths for substrings of a string

 Calling Sequence Border( w ) BorderLength( w ) BorderArray( w )

Parameters

 w - Maple string

Description

 • The Border( w ) command computes the border of a string w. The border of a string (or word)  w is the maximal prefix of w that is also a suffix of w.
 • The BorderLength( w ) command computes only the length of the border of the word w. It is, by definition, equal to length( Border( w ) ), but is more space efficient because the string Border( w ) is not constructed.
 • The BorderArray( w ) command computes a list of border lengths for the length( w ) substrings of w, where the ith substring consists of the first i characters of w. That is, BorderArray( w ) is equal to $[\mathrm{BorderLength}\left({w}_{1}\right),\mathrm{BorderLength}\left(w[1\mathrm{..}2]\right),...,\mathrm{BorderLength}\left(w[1\mathrm{..}\mathrm{length}\left(w\right)]\right)]$.
 • 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

 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{Border}\left(""\right)$
 ${""}$ (1)
 > $\mathrm{Border}\left("aaa"\right)$
 ${"aa"}$ (2)
 > $\mathrm{Border}\left("ababab"\right)$
 ${"abab"}$ (3)
 > $\mathrm{Border}\left("ab"\right)$
 ${""}$ (4)
 > $\mathrm{Border}\left("aba"\right)$
 ${"a"}$ (5)
 > $\mathrm{Border}\left("abcab"\right)$
 ${"ab"}$ (6)
 > $\mathrm{BorderLength}\left("abcab"\right)$
 ${2}$ (7)
 > $\mathrm{BorderArray}\left("abcab"\right)$
 $\left[{0}{,}{0}{,}{0}{,}{1}{,}{2}\right]$ (8)
 > $\mathrm{BorderArray}\left("aaaab"\right)$
 $\left[{0}{,}{1}{,}{2}{,}{3}{,}{0}\right]$ (9)
 > $N≔100000:$
 > $\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20,'\mathrm{binary}'\right)\right),i=1..N\right)}{N}\right)$
 ${1.630930000}$ (10)
 > $\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20,'\mathrm{dna}'\right)\right),i=1..N\right)}{N}\right)$
 ${0.4214100000}$ (11)
 > $\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20,'\mathrm{lower}'\right)\right),i=1..N\right)}{N}\right)$
 ${0.04103000000}$ (12)
 > $\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20,'\mathrm{print}'\right)\right),i=1..N\right)}{N}\right)$
 ${0.01095000000}$ (13)
 > $\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20\right)\right),i=1..N\right)}{N}\right)$
 ${0.003670000000}$ (14)