String Matching with Sliding Window

Naive String Search

def naive_search(text, pattern):
    for i in range(len(text) - len(pattern)):
        if text[i:i+len(pattern)] == pattern:
            return i
    return -1

Time: O(n*m) where n=text, m=pattern
Slow for large text!

Rabin-Karp Algorithm

Use hash values instead of string comparison:

text = "ABABCABABA"
pattern = "ABA"

Calculate hash of pattern
Slide window, calculate each hash
Compare hashes (O(1) instead of O(m))

Time: O(n + m) average case!

KMP Algorithm

Knuth-Morris-Pratt uses failure function:

If mismatch: Don't restart from beginning
Jump to known safe position

text = "ABABCABABA"
pattern = "ABAB"

ABAB...
    ↓ mismatch
Jump to position based on overlaps!

Practical Applications

1. Text search (Ctrl+F)
2. DNA sequence matching
3. Plagiarism detection
4. Autocomplete & search engines
5. Network packet inspection
6. Video/image recognition

Complexity Comparison

Algorithm     | Time         | Space
────────────────────────────────────
Naive         | O(n*m)       | O(1)
Rabin-Karp    | O(n+m)       | O(1)
KMP           | O(n+m)       | O(m)
Boyer-Moore   | O(n/m)       | O(m)