String Matching / Pattern Matching

LeetCode #28 [Easy]

Problem Statement

Given a text string txt and a pattern pat, find all occurrences of the pattern in the text.

Example: Input: txt = "ababcabc", pat = "abc" → Output: [2,5]

Approach 1: Brute Force

Explanation: Check every substring of txt of length len(pat) for equality.

Time Complexity: O(n*m) where n=len(txt), m=len(pat)

Space Complexity: O(1)

for i = 0 to n-m:
    if txt[i..i+m-1] == pat:
        add i to result
return result
Heap Sort Flowchart

💡 Think: Slide the pattern over text and compare characters at every position.

Approach 2: Rabin-Karp Algorithm

Explanation: Use rolling hash to compare pattern and substring efficiently.

Time Complexity: O(n) average, O(n*m) worst-case

Space Complexity: O(1)

hash_pat = hash(pat)
for i = 0 to n-m:
    hash_sub = hash(txt[i..i+m-1])
    if hash_sub == hash_pat and txt[i..i+m-1] == pat:
        add i to result
return result
Heap Sort Flowchart

💡 Think: Use rolling hash to filter quickly; verify on hash matches only.

Approach 3: KMP Algorithm (Optimal)

Explanation: Preprocess pattern to create lps array, then traverse txt to find matches efficiently.

Time Complexity: O(n+m)

Space Complexity: O(m)

build lps array for pat
i = 0, j = 0
while i < n:
    if txt[i] == pat[j]:
        i++, j++
        if j == m:
            add i-j to result
            j = lps[j-1]
    else if j != 0:
        j = lps[j-1]
    else:
        i++
return result
Heap Sort Flowchart

💡 Think: Precompute LPS to skip redundant checks and scan text in linear time.

Solve on LeetCode