{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm{{ algorithmLabel }} Comparisons{{ resultsReady ? computation.values.search_comparison_count : '—' }} Trace steps{{ resultsReady ? traceRows.length : '—' }}
The work profile runs all four methods on the same literal input.
Use 0 to 80 Unicode code points. The empty text is a valid no-match case.
Use 1 to 20 Unicode code points. Overlapping matches are retained.

Samples replace the literal text and pattern while keeping the selected algorithm.

The neutral default is 500 ms between canonical trace frames.
Step {{ traceCursor + 1 }} of {{ traceRows.length }}
{{ displayPoint(point) }}
{{ displayPoint(patternPointAt(column - 1)) }}
{{ currentTrace.kind.replaceAll('_', ' ') }}
{{ currentTraceLabel }}
{{ currentTrace.message }}
{{ displayPoint(row.label) }}{{ row.value }}

The chart renderer is unavailable. The same counts remain available in the exported CSV and summary.

StepDecisionAlignmentCompared pairExplanationCopy
{{ row.step }}{{ row.decision }}{{ row.alignment }}{{ row.pair }}{{ row.explanation }}
Search Algorithm Simulator Compare four search methods with repeatable probe traces and see how candidate ranges, data order and duplicates affect first-match or miss results.
Dynamic Programming Algorithm Simulator Explore memoization and tabulation for three classic problems through state tables, exact recurrences, and traceable solution choices.
Hash Table Operations Simulator Trace hash-table insert, search, and delete operations across chaining and probing strategies with collision and tombstone evidence.
Regex Tester Test JavaScript regular expressions against text or files with match and capture-group evidence, replacement previews, and timeout-protected runs.

Exact string matching looks for every position where a pattern appears as a contiguous part of a longer text. The result depends on literal character order, not on word meaning. Case changes, accents, normalization differences, and invisible characters can therefore turn text that looks similar into a different sequence.

A simple matcher tests the pattern at every possible alignment. Faster methods avoid some repeated work by learning from the pattern or from a compact summary of the current text window. Knuth–Morris–Pratt (KMP) reuses matched prefixes, Rabin–Karp filters windows with a rolling hash, and Boyer–Moore–Horspool compares from the pattern's right edge and shifts past unpromising alignments.

Alignment
A possible starting position for the pattern within the text.
Preprocessing
Work performed on the pattern before or alongside the main comparisons, such as an LPS or shift table.
Fallback
A KMP move to a shorter reusable prefix after a mismatch or completed match.
Hash collision
A Rabin–Karp window with the same hash as the pattern but different literal code points.

Overlapping matches are valid. In BANANA, the pattern ANA starts at code-point indices 1 and 3. Recording the first match must not skip the second alignment, so the fallback or shift rule after a match matters as much as mismatch handling.

Unicode code points provide a more useful unit than UTF-16 code units for an educational trace, but a code point is not always a complete user-perceived character. A letter plus a combining mark can occupy two code points, and visually identical text can use different normalization forms. Literal matching does not correct those differences.

Operation counts describe these specific trace rules and inputs. They do not measure elapsed time, allocation cost, optimized library behavior, processor effects, or the cost of preparing text for a production search.

How to Use This Tool:

Use the same literal text and pattern when comparing methods; only the algorithm should change.

  1. Choose Naive, KMP, Rabin–Karp, or Boyer–Moore–Horspool under Algorithm.
  2. Enter 0 to 80 Unicode code points in Text. An empty text is a valid no-match case.
  3. Enter a nonempty Pattern of 1 to 20 code points. Matching is literal and case-sensitive; overlapping starts are retained.
  4. Step through or play the trace. Follow the current alignment, compared text and pattern indices, equality result, preprocessing entries, fallback, shift, or hash-verification decision.
  5. Read the final match starts and then compare the work profile. Keep text, pattern, and character form unchanged so differences come from the algorithms rather than different inputs.

Interpreting Results:

Match starts are zero-based code-point indices. A result of No literal match means no complete alignment matched exactly; it does not mean the words are unrelated or that a case-insensitive, normalized, locale-aware, or regular-expression search would also fail.

Search comparisons, preprocessing comparisons, shifts, fallbacks, hash candidates, verified candidates, and collisions measure different kinds of work. Do not add them casually into a universal speed score. KMP may spend more work preprocessing, while Rabin–Karp may inspect many hashes but perform few literal comparisons.

A Rabin–Karp hash agreement is only a candidate. The literal verification decides whether the alignment is a match; collision evidence shows why the hash alone cannot be trusted.

Technical Details:

The text and pattern are split into Unicode code points and compared without case folding or normalization. Every algorithm reports all literal match starts under the same indexing rule, which makes their traces comparable even though their preprocessing and shift decisions differ.

Transformation Core:

Algorithm Prepared evidence Search direction and shift rule Match handling
NaiveNo tableCompare left to right; after each alignment, shift by 1.Record a complete alignment and continue, preserving overlaps.
KMPLongest proper prefix that is also a suffix (LPS) length at each pattern indexCompare left to right; on mismatch, reuse the longest valid prefix instead of restarting the text scan.After a match, fall back through the LPS value so overlaps remain possible.
Rabin–KarpPattern hash, rolling text-window hash, base 257, and modulus 101Shift by 1 while updating the window hash from the outgoing and incoming code points.Verify every equal-hash window literally; reject unequal content as a collision.
Boyer–Moore–HorspoolShift distance for code points before the pattern's final positionCompare right to left; shift by the distance assigned to the current window-end code point, or by the full pattern length when absent.Record a full right-to-left match, then apply the same window-end shift rule.

Formula Core:

Rabin–Karp maps each code point to its numeric value plus 1, then evaluates a polynomial hash. For a pattern or window of length m, base b is 257 and modulus q is 101.

H(s)= ∑i=0m−1 v(si) bm−1−i modq

The next window removes the outgoing code point's highest-place contribution, multiplies by the base, and adds the incoming code point. Modulo correction keeps the intermediate value non-negative.

Hk+1= ( (Hk−v(tk)bm−1) b+v(tk+m) )modq

Because the modulus is deliberately small enough to make collisions visible in a teaching trace, equal hashes never bypass literal comparison.

Boundary Rules:

  • If the pattern is longer than the text, no candidate alignment exists.
  • An empty text with a nonempty pattern is valid and produces no match.
  • An empty pattern is invalid rather than being treated as a match at every boundary.
  • Text is limited to 80 code points and the pattern to 20 code points so traces remain bounded.
  • Playback interval changes animation timing only; it does not change matches or operation counts.

Worked Examples:

Overlapping matches

With text BANANA and pattern ANA, the complete literal matches start at code-point indices 1 and 3. KMP's post-match fallback and the other algorithms' continuing shifts preserve the second, overlapping result.

Emoji code-point indexing

With text A😀B😀A😀 and pattern 😀A, the match starts at code-point index 3. UTF-16-based indexes in another program may differ because each emoji can occupy a surrogate pair there.

References: