Skip to content
Hello Python
Algorithm1 Practice1 Interview

String Matching

Locate pattern occurrences in text while controlling repeated comparison work. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider String Matching when the prompt's constraints and required operations match this shape: Locate pattern occurrences in text while controlling repeated comparison work.

Pybit demonstrates String Matching in a professional Python interview workspace.
On this page · Define Pattern Alignment and Match Semantics

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

String Matching Code Labs

Define Pattern Alignment and Match Semantics

String matching asks where a pattern aligns with consecutive text symbols. Define first versus all matches, overlapping behavior, case normalization, and the empty-pattern result before selecting an algorithm.

Reuse Information after a Mismatch

Naive matching advances one alignment and repeats comparisons. KMP reuses a prefix-suffix table, while Rabin-Karp reuses a rolling fingerprint and verifies candidates.

Trace Naive Pattern Alignments

Reference
def alignment_trace(text,pattern):
    if pattern=="":return [[0,0]]
    trace=[]
    for start in range(len(text)-len(pattern)+1):
        matched=0
        while matched<len(pattern) and text[start+matched]==pattern[matched]:matched+=1
        trace.append([start,matched])
        if matched==len(pattern):break
    return trace
Practice

Implement alignment_trace(text,pattern). Return [start,matched_prefix_length] for each alignment through the first full match.

Public tests

  • Measure each mismatch alignment

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Prefix Hash or Automaton State

Choose direct comparison for short inputs, KMP for deterministic linear worst-case matching, rolling hash for many same-length windows, or an automaton/trie for multiple patterns.

Find First Pattern Occurrence

Reference
def find_pattern(text,pattern):
    if pattern=="":return 0
    for start in range(len(text)-len(pattern)+1):
        if all(text[start+offset]==character for offset,character in enumerate(pattern)):return start
    return -1
Practice

Implement find_pattern(text,pattern). Return the first start index or -1, with empty pattern at zero.

Public tests

  • Honor first and empty-pattern semantics

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle Empty Patterns and Unicode

Common search APIs define the empty pattern at index zero. Python string indexes count Unicode code points, not grapheme clusters; normalization may be needed when visually equivalent text must match.

Explain It in an Interview

Say: “An alignment begins at this text index. On mismatch, this algorithm reuses this precise prior information instead of restarting blindly.” State empty behavior, overlap policy, alphabet assumptions, and complexity in text and pattern lengths.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The String Matching proof does not depend on a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
String Matching complete workflowO((n-m+1)m)O((n-m+1)m)Try each legal start and compare pattern characters until mismatch or completion.

Space

O(k) for the focused Find Every String Match implementation.

Assumptions

  • Every possible match begins at one enumerated legal alignment. The inner comparison accepts exactly when all pattern positions agree, so all and only matches are returned, including overlaps.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise String Matching invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The retained prefix or hash state represents exactly the current candidate alignment.
  3. Text positions already passed cannot begin an unreported match.
  4. Enumerate exactly the legal alignments. Preserve this claim after every transition.
  5. Preserve overlapping and empty-pattern matches. Preserve this claim after every transition.

When To Use Or Avoid String Matching

Use It When

  • Use String Matching when this precondition is stated or can be proved: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
  • Use it when this maintained state removes repeated work: The retained prefix or hash state represents exactly the current candidate alignment.

Choose Another Tool When

  • Avoid String Matching when this precondition is absent: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.

Avoid

def find_occurrences(text, pattern):
    pass

Use instead

def find_occurrences(text, pattern):
    matches = []
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset, character in enumerate(pattern):
            if text[start + offset] != character:
                matched = False
                break
        if matched:
            matches.append(start)
    return matches

Where you will hit this: Find Every String Match(opens in a new tab)

Breaking the state transition

Advances by pattern length and skips overlapping matches.

Prevent it: Preserve this proof obligation: Every skipped comparison is represented by an already verified prefix or a collision-checked hash candidate.

Avoid

def find_occurrences(text,pattern):
    out=[]; i=0
    while i+len(pattern)<=len(text):
        if text[i:i+len(pattern)]==pattern:out.append(i);i+=len(pattern)
        else:i+=1
    return out

Use instead

def find_occurrences(text, pattern):
    matches = []
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset, character in enumerate(pattern):
            if text[start + offset] != character:
                matched = False
                break
        if matched:
            matches.append(start)
    return matches

Where you will hit this: Find Every String Match(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O((n-m+1)m).

Avoid

def find_occurrences(text,pattern):
    out=[]; i=0
    while i+len(pattern)<=len(text):
        if text[i:i+len(pattern)]==pattern:out.append(i);i+=len(pattern)
        else:i+=1
    return out

Use instead

def find_occurrences(text, pattern):
    matches = []
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset, character in enumerate(pattern):
            if text[start + offset] != character:
                matched = False
                break
        if matched:
            matches.append(start)
    return matches

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.