String

A word over an alphabet $\Sigma$ is a finite sequence of symbols from $\Sigma$. The empty word has length zero, and ${\Sigma }^{\ast }$ denotes the set of all finite words.

A string suffix consists of all characters from some position to the end of a string. For example, TAC has suffixes TAC, AC, C and the empty string. Sorting these in lexicographic order groups all suffixes beginning with a given query into one interval.

A cyclic rotation of a string $xy$ is the string $yx$, where $x$ and $y$ are consecutive pieces. For example, rotating ABC left once gives BCA. A length-$n$ string has $n$ rotation positions, though repeated letters can make some resulting strings identical.

A substring is a contiguous segment of a string. It differs from a subsequence, whose selected characters need not be adjacent.

An infinite binary word is Sturmian if it has exactly $n+1$ distinct contiguous subwords of length $n$ for every positive integer $n$.

A palindrome is a finite string equal to its reversal. For example, the strings $010$ and $0110$ are palindromes.

Decide whether a finite string is a palindrome by comparing corresponding symbols from opposite ends. The test needs at most half as many symbol comparisons as the string length and can use constant auxiliary space.

Concatenation joins two strings end to end, retaining the order of their symbols. For example, joining $ab$ and $ba$ gives $abba$. It has the associative property: joining $(uv)w$ or $u(vw)$ gives the same word over an alphabet. The empty word is its identity element. All finite words over an alphabet with this binary operation form a free monoid.

The length of a word over an alphabet is the number of symbol positions in that finite string, counting repetitions. Thus $\ell (abba)=4$ and $\ell (\epsilon )=0$ for the empty word. Concatenation satisfies $\ell (uv)=\ell (u)+\ell (v)$. This differs from the word length of a group element, which minimizes over representing words using a chosen generating set of a group.

A run of a word over an alphabet is a maximal consecutive block of one repeated letter. For a nonempty word $w$ of length $N$, its number of runs isReplacing a consecutive constant block changes this count only through its boundaries with the neighboring letters.

A border of a word is a nonempty prefix that is also a suffix. The full word is counted as a border; a shorter border records a way in which one occurrence can overlap the next.