Selfoverlap

Selfoverlap, in the context of string processing and formal language theory, refers to an overlap between a string and itself. Concretely, for a string w over an alphabet, a border is a nonempty string b that occurs as both a prefix and a suffix of w, with length less than the length of w. The longest such border is called the longest self-overlap of w. If no nontrivial border exists, the string has no proper self-overlap.

Formally, let w be a string. A border b of w satisfies w starts with b and ends with b, and 0 < |b| < |w|. The length ℓ(w) of the longest border is the maximum t such that the prefix of w of length t equals the suffix of w of length t. This concept is central to understanding the self-overlap structure of a string and to determining its periodicity.

Self-overlaps have practical importance in algorithms for pattern matching and text processing. They underpin the construction of the prefix function (or border array) used by the Knuth–Morris–Pratt algorithm to efficiently skip characters during search. They also arise in applications such as DNA sequence analysis, where overlapping reads or segments may align with themselves under certain operations. A string with a longer border exhibits stronger periodicity, with a period p = |w| − ℓ(w) when ℓ(w) > 0.

See also: border, prefix function, Z-function, pattern matching, string algorithms.