Overview
The prefix function records, for each position, the length of the longest proper prefix that is also a suffix ending there. This preprocessing is central to KMP-style string matching.
CoreSource checked
Prefix Function
Computes the longest proper border length for every prefix of a string.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- String Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pattern preprocessingstring matchingmatchingpattern matching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)
When to Use
- Use when border information is needed for linear-time string matching or repetition analysis.
- Use when overlapping pattern matches must be handled without rescanning.
When Not to Use
- Avoid when a one-off tiny string is clearer with direct comparison.
- Avoid when approximate matching or scored alignment is required.
What It Does
- Tracks border lengths for each prefix
- Falls back through previous borders after mismatches
- Builds preprocessing data in linear time
Use Cases
- KMP pattern preprocessing
- Finding repeated prefix-suffix structure
- String periodicity checks
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Pseudocode
- 1.Set pi[0] = 0
- 2.For each position i from 1 to n - 1
- 3.Set j = pi[i - 1]
- 4.While j > 0 and s[i] != s[j], set j = pi[j - 1]
- 5.If s[i] == s[j], increment j
- 6.Set pi[i] = j
Canonical Example
- Input
- string 'ababaca'
- Output
- prefix values [0, 0, 1, 2, 3, 0, 1]
- Explanation
- At each position, the value is the longest prefix that is also a suffix ending there.
Implementation Notes
- Use zero-based indexes consistently.
- For mismatch at position i, fall back from j to pi[j - 1].
- Test strings such as 'aaaa' and 'ababaca'.
Common Pitfalls
- Confusing proper borders with the full prefix itself.
- Fallback loops must use previous prefix values, not restart from scratch.
- Empty strings and repeated characters need explicit tests.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow computing the longest proper border for every prefix on a small pattern preprocessing example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: Set pi[0] = 0
pattern-matching-mechanismNotes
The prefix function is preprocessing; KMP uses it to decide how far the pattern can shift after a mismatch.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Prefix Function's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Prefix Function's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toShift-And Algorithm
Pattern Matching · Core
Prefix Function and Shift-And Algorithm solve related pattern preprocessing problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBit-Parallel Levenshtein
Prefix Function and Bit-Parallel Levenshtein solve related pattern preprocessing problems with different assumptions and tradeoffs.
Alternative toShift-And Algorithm
Prefix Function and Shift-And Algorithm solve related pattern preprocessing problems with different assumptions and tradeoffs.
Alternative toShift-Or Algorithm
Prefix Function and Shift-Or Algorithm solve related pattern preprocessing problems with different assumptions and tradeoffs.
Tags
Pattern MatchingStringsMatching