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.

$\mathrm{with}\left(\mathrm{StringTools}\right)\:$

$\mathrm{Border}\left(''''\right)$

$\mathrm{Border}\left(''aaa''\right)$

$''aa''$

$\mathrm{Border}\left(''ababab''\right)$

$''abab''$

$\mathrm{Border}\left(''ab''\right)$

$\mathrm{Border}\left(''aba''\right)$

$''a''$

$\mathrm{Border}\left(''abcab''\right)$

$''ab''$

$\mathrm{BorderLength}\left(''abcab''\right)$

$2$

$\mathrm{BorderArray}\left(''abcab''\right)$

$\left[0\,0\,0\,1\,2\right]$

$\mathrm{BorderArray}\left(''aaaab''\right)$

$\left[0\,1\,2\,3\,0\right]$

$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$

$\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$

$\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$

$\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$

$\mathrm{evalf}\left(\frac{\mathrm{add}\left(\mathrm{BorderLength}\left(\mathrm{Random}\left(20\right)\right)\,i=1..N\right)}{N}\right)$

$0.003670000000$