Overview
Sunday Quick Search compares the current text window with the pattern, then uses the character immediately following the window to choose the next shift.
CoreSource checked
Sunday Quick Search
Searches for a pattern by shifting according to the character just after the current window.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- String Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
exact string matchingstring 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 for exact string search when a simple bad-character style shift is enough.
- Use when the text can be indexed one character past the current window safely.
When Not to Use
- Avoid when streaming input prevents looking past the current window.
- Avoid when worst-case guarantees are more important than simple average-case behavior.
What It Does
- Computes string matching within String Matching workloads (O(n + m) time, O(n + m) space).
- Works by Searches for a pattern by shifting according to the character just after the current window.
- Maintains key invariants across exact string matching, string matching, matching.
Use Cases
- Production and research workloads requiring string matching via Searches for a pattern by shifting according to the character just after the current window.
- String Matching 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 matching.
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Pseudocode
- 1.Build the Sunday shift table
- 2.Set window start i = 0
- 3.While the pattern fits in the text
- 4.Compare pattern with text window at i
- 5.If all characters match, report i
- 6.Otherwise shift by the table entry for the character after the window
Canonical Example
- Input
- pattern 'abc', text 'zzabc'
- Output
- match at index 2
- Explanation
- After a failed window, the next character determines how far the pattern can shift.
Implementation Notes
- Precompute shift[c] from the rightmost occurrence of c in the pattern.
- Compare the full pattern at each window position.
- If no match, inspect text[i + pattern.length] to shift.
Common Pitfalls
- The shift character is after the window, not inside the mismatched position.
- The last window needs bounds checks before reading the following character.
- Missing alphabet entries should shift by pattern length plus one.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow shifting based on the character immediately after the current window on a small exact string matching example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: Build the Sunday shift table
pattern-matching-mechanismNotes
Sunday Quick Search is simple and often fast, but it is still an exact matching method with ordinary worst-case caveats.
Sources (1)
What each reference supports for this entry.
Sunday Quick Search
PaperOriginal reference for Quick Search shifts and right-context character lookups.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toShift-And Algorithm
Pattern Matching · Core
Sunday Quick Search and Shift-And Algorithm solve related exact string matching problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBit-Parallel Levenshtein
Sunday Quick Search and Bit-Parallel Levenshtein solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toShift-And Algorithm
Sunday Quick Search and Shift-And Algorithm solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toShift-Or Algorithm
Sunday Quick Search and Shift-Or Algorithm solve related exact string matching problems with different assumptions and tradeoffs.
Tags
Pattern MatchingStringsMatching