CoreSource checked

Two-Way String Matching

Searches exactly by splitting the pattern at a critical factorization and scanning in two directions.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Exact String Matching
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

The Two-Way algorithm computes a critical factorization of the pattern, then uses period information to skip safely while checking the right and left parts of the pattern.

Core Concepts

exact string matchingmatchingfactorizationpattern 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 exact string matching with linear worst-case behavior is desired.
Use when preprocessing one pattern and scanning a long text.

When Not to Use

Avoid when a simpler matcher is easier and worst-case behavior is not a concern.
Avoid when approximate matching or edit distance is required.

What It Does

Computes exact string matching within Exact String Matching workloads (O(n + m) time, O(n + m) space).
Works by Searches exactly by splitting the pattern at a critical factorization and scanning in two directions.
Maintains key invariants across exact string matching, matching, factorization.

Use Cases

Production and research workloads requiring exact string matching via Searches exactly by splitting the pattern at a critical factorization and scanning in two directions.
Exact 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 exact string matching.

Inputs

Text or sequence
Pattern, index, or comparison sequence

Outputs

Matches, alignment, index, or similarity value

Pseudocode

1.Compute a critical factorization and period for the pattern
2.Set the text window start
3.Compare the right part of the pattern
4.If it matches, compare the left part
5.Report a full match or shift by the safe period rule
6.Continue until the pattern no longer fits

Canonical Example

Input: pattern 'abab', text 'zzababz'
Output: match at index 2
Explanation: The factorization and period let the search skip safely after failed checks.

Implementation Notes

Implement maximal suffix and period computation as a tested helper.
Test highly periodic patterns such as 'ababab'.
Keep the memory optimization separate from correctness first.

Common Pitfalls

Critical factorization and period computation are easy to implement incorrectly.
Indexes for the left and right checks must stay consistent.
Periodic and nonperiodic cases use different safe shift rules.