Prefixfunktionen

Prefixfunktionen, also known as the prefix function, is a concept in string processing used to describe borders of prefixes of a string. For a string s of length n, the value pi[i] (i from 0 to n-1) is defined as the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i]. A border is a substring that is both a prefix and a suffix of the considered prefix. By convention pi[0] = 0, since a single character has no nontrivial border.

Computation and complexity: The prefixfunktionen can be computed in linear time with a single pass over the string. Typically an index j tracks the length of the current candidate border. For i from 1 to n-1, while j > 0 and s[i] != s[j], set j to pi[j-1]. If s[i] == s[j], increment j. Then set pi[i] = j. This algorithm runs in O(n) time and uses O(n) space for the resulting pi array.

Applications and relationships: The prefixfunktionen is a core component of the Knuth–Morris–Pratt (KMP) string matching algorithm, where the pi array guides the shift of the pattern upon mismatches, enabling linear-time search. It is related to the Z-function, another preprocessing tool for pattern matching, but computes border information in a different form.

Example: for the string s = "ababaca", the prefixfunktionen values are pi = [0, 0, 1, 2, 3, 0, 1]. Each entry pi[i] gives the length of the longest border of the prefix s[0..i].

Variations and terminology: While "prefixfunktion" and "pi" are common terms, implementations may vary slightly in indexing conventions or in whether the entire prefix is considered a border.