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 comparison of strings that disregards a chosen distinction between uppercase and lowercase characters. A simple convention compares characterwise lowercase forms. Full Unicode case folding is a distinct normalization operation and can change character counts.

The longest common prefix of two strings is the longest string that is a string prefix of both. Its length is the number of matching initial characters before the first mismatch or the end of a string. A direct scan maintains equality of the processed prefixes and takes time linear in that length plus one. For suffixes represented by indices in a shared array, no character copying is needed.

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.

String rewriting transforms a string by replacing an occurrence of the left side of a rule $\ell \to r$ with its right side, leaving the surrounding context unchanged. A system may offer several applicable rules or positions, so a reduction need not be deterministic.

For example, $ab\to ba$ changes $aab$ to $aba$ and then $baa$. A system is terminating if no infinite chain of rewrites exists; it is confluent if any two results reached from the same string can be rewritten to a common result. Together these properties give a unique irreducible normal form. This is useful for deciding equality in algebraic presentations and for implementing symbolic simplification.

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

For an irrational number $0<\alpha <1$, the characteristic Sturmian word of slope $\alpha$ is the binary sequenceEach term is zero or one because the arguments differ by less than one. This fixes an intercept convention: it is the lower mechanical word with intercept $\alpha$.

For $\alpha =(3-\sqrt{5})/2$, the beginning is $0100101001\dots$, the Fibonacci word. Like every Sturmian word, it has exactly $n+1$ distinct factors of length $n$. Its relation to continued fractions makes its recursive block structure reflect the partial quotients of its slope.

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.

An anagram of a finite string is another string with exactly the same number of occurrences of each symbol. Thus $aab$ and $aba$ are anagrams; $abb$ is not. Equivalently, the second string is obtained by a permutation of the positions.

If a length-$n$ string has symbol multiplicities $m_1,\dots ,m_r$, its number of distinct anagrams is the multinomial coefficient $n!/(m_1!\cdots m_r!)$. Dividing by the factorials removes position permutations that only exchange equal symbols. The count depends on multiplicities, not the original ordering.

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.