Overview
Kasai's algorithm builds inverse suffix-array ranks and reuses the previous longest-common-prefix length, decreasing it by one before extending the next comparison.
CoreSource checked
Kasai LCP Algorithm
Computes the LCP array from a suffix array in linear time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- String Indexing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
longest common prefix arraystring indexingsuffix structurepattern 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 after constructing a suffix array when adjacent suffix LCP values are needed.
- Use when linear-time LCP construction is preferable to comparing suffixes from scratch.
When Not to Use
- Avoid when a suffix tree or suffix automaton already provides the needed query directly.
- Avoid when memory for rank and LCP arrays is not available.
What It Does
- Kasai LCP Algorithm uses reusing previous prefix length while scanning suffix ranks for longest common prefix array
- Organizes the work around longest common prefix array and string indexing.
Use Cases
- Production and research workloads requiring string indexing via one before extending the next comparison.
- String Indexing pipelines where O(n + m) time and O(n + m) space fit system constraints.
- Engineering comparisons against Bit-Parallel Levenshtein and Shift-And Algorithm when tuning string indexing.
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Key Formulas (1)
LCP reuse
h = max(h − 1, 0) before extending next suffix pair
h = max(h - 1, 0) before extending next suffix pairReuses all but one character of the previous longest common prefix.
Pseudocode
- 1.Build rank for each suffix start position
- 2.Set h = 0
- 3.For each text position i
- 4.If rank[i] is the last suffix, continue
- 5.Compare suffix i with the next suffix while characters match
- 6.Store h as the LCP for rank[i]
- 7.If h > 0, decrement h
Canonical Example
- Input
- text 'banana' and suffix array [5,3,1,0,4,2]
- Output
- LCP values [1,3,0,0,2] between adjacent suffixes
- Explanation
- Adjacent sorted suffixes such as 'ana' and 'anana' share prefix 'ana'.
Implementation Notes
- Build rank[pos] so rank maps a suffix start to its suffix-array index.
- Compare suffix i with the next suffix in suffix-array order.
- After each position, reduce the current LCP length by one if positive.
Common Pitfalls
- The final suffix in suffix-array order has no next suffix for comparison.
- Rank array indexes must map original positions to suffix-array positions.
- Forgetting to decrement the reused LCP length breaks linear-time behavior.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow reusing previous prefix length while scanning suffix ranks on a small longest common prefix array example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 7: Build rank for each suffix start position
pattern-matching-mechanismNotes
Kasai's algorithm assumes the suffix array is already correct; it only builds the adjacent LCP array.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Kasai LCP Algorithm's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Kasai LCP Algorithm'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
Both address longest common prefix array, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBit-Parallel Levenshtein
Both address longest common prefix array, but they make different modeling or performance tradeoffs.
Alternative toShift-And Algorithm
Both address longest common prefix array, but they make different modeling or performance tradeoffs.
Alternative toShift-Or Algorithm
Both address longest common prefix array, but they make different modeling or performance tradeoffs.
Tags
Pattern MatchingStrings