ababaca

ababaca is a seven-letter string constructed from the letters a, b, and c. It is widely used in computer science as a canonical example in the study of pattern matching algorithms, particularly the Knuth–Morris–Pratt (KMP) algorithm. The string is used to illustrate how the algorithm computes the prefix function, also known as the partial-match table, and how the derived failure function guides pattern shifts after mismatches.

For ababaca, the prefix function values are 0, 0, 1, 2, 3, 0, 1. Interpreted for each prefix length i (1-based), pi[i] equals the length of the longest proper prefix that is also a suffix of the prefix P[1..i]. This yields the sequence: pi1=0, pi2=0, pi3=1, pi4=2, pi5=3, pi6=0, pi7=1.

These values demonstrate nontrivial overlaps and how the KMP preprocessing enables linear-time search by avoiding unnecessary re-checks. The example is also used to explain border concepts in strings, where a border is a non-empty string that is both a prefix and a suffix of the examined substring.

Outside theoretical discussions, ababaca is generally treated as a conventional demonstration input; it has no intrinsic semantic meaning in natural language. The pattern is valued for its repeating structure that yields a varied but predictable prefix-function progression.