ReviseAlgo Logo

Strings

Pattern Matching Algorithms

Master string searching algorithms: Naive Brute Force, Rabin-Karp Rolling Hash, and the KMP (Knuth-Morris-Pratt) algorithm with LPS tables.

Last Updated: August 2, 2026 • 30 min read

1. Introduction

What is Pattern Matching?

Pattern Matching is the problem of finding all occurrence indices of a pattern string P (length M) inside a text string T (length N).

Why is it Important?

Naive pattern matching tests every starting index in text T, taking O(N × M) time. Advanced algorithms like Rabin-Karp and KMP (Knuth-Morris-Pratt) guarantee linear O(N + M) time by avoiding repeated comparisons of characters already inspected.

Where is it Used?

  • Text Search (ctrl+F / grep): Searching keywords in massive text files.
  • Plagiarism & Intrusion Detection: Detecting signature attack payloads in network traffic packets.

    • 2. Mental Model

    Imagine reading a long manuscript looking for the word "AAAA":

    When a mismatch occurs at the 5th character ('B' vs 'A'), a naive reader slides back to index 1 and re-reads 'A A A' all over again.

    A KMP reader remembers: "I already matched 3 'A's! I don't need to re-read them from scratch—I can jump straight ahead!" This memory is stored in the LPS (Longest Prefix Suffix) table.

    3. Concept: The Three Main Search Algorithms

    1. Naive Brute-Force Matching — O(N × M)

    Check every possible starting alignment i from 0 to N - M.

    2. KMP (Knuth-Morris-Pratt) Algorithm — O(N + M) Time

    KMP builds a Longest Prefix Suffix (LPS) array of size M. lps[i] stores the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].

    4. Visuals

    Algorithm Comparison Table

    AlgorithmPrecomputation TimeSearch Time ComplexityAuxiliary SpaceKey Advantage
    Naive SearchNoneO(N × M)O(1)Simple to write
    Rabin-KarpO(M)O(N + M) avg / O(N × M) worstO(1)Multi-pattern search & rolling hash
    KMP AlgorithmO(M)O(N + M) guaranteedO(M)Zero text pointer backtracking

    KMP LPS Table Construction for "AAAA" vs "ABAB"

    5. Real-World Examples

  • Virus & Malware Scanners: Comparing file binary byte streams against known virus signature pattern databases using Rabin-Karp rolling hashes.
  • DNA Motif Finding: Locating sub-gene sequences inside multi-gigabyte chromosome text dumps in guaranteed linear time via KMP.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test pattern matching via questions like LeetCode 28: "Implement strStr() / find needle in haystack".

    Common Mistakes

    Warning: 1. Resetting Text Pointer i in KMP: In KMP, the text pointer i NEVER moves backward! Only the pattern pointer j jumps back to lps[j - 1].
    > 2. Integer Overflow in Rolling Hash: In Rabin-Karp, modular arithmetic (mod 10^9 + 7) must be applied at every step to prevent integer overflow during hash computation.

    7. Summary

  • Naive Search: O(N × M) worst case when text and pattern contain repeated characters.
  • KMP Algorithm: Uses an O(M) LPS table to guarantee O(N + M) runtime without resetting the text index pointer.
  • Rabin-Karp: Rolling hash technique ideal for multi-pattern searching.

    • 8. Quiz

    Question 1: What does lps[k] store in the KMP algorithm? Answer: The length of the longest proper prefix of pattern[0..k] that is also a suffix of pattern[0..k].
    Question 2: What is the worst-case time complexity of the Naive Pattern Matching algorithm on Text = "AAAAAAAB" and Pattern = "AAAA"? Answer: O(N × M) where N is text length and M is pattern length.
    Question 3: Does the text index pointer i ever move backward during a KMP search? Answer: No! In KMP, i moves strictly forward from 0 to N-1. Only the pattern index j shifts backward using the LPS table.
    Question 4: What is the time complexity of building the KMP LPS array for a pattern of length M? Answer: O(M) time.
    Question 5: What is a Rolling Hash in the Rabin-Karp algorithm? Answer: A hash function that computes the hash value of the next sliding window in O(1) time by subtracting the leading character and adding the trailing character.