# String Matching — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/string-matching

> Text में pattern को कुशलता से खोजना — KMP का failure function और Rabin-Karp hashing पर एक नज़र।

## Brute force क्यों नहीं?

Pattern को text पर सादगी से खिसकाकर तुलना करना `O(n*m)` है। **KMP (Knuth-Morris-Pratt)**, pattern के लिए पहले से गणना करके कि mismatch पर कितना पीछे जाना है, पहले से मिले characters को दोबारा जांचने से बचता है — `O(n + m)` देता है।

## KMP failure function

`lps[i]` उस सबसे लंबे उचित prefix की लंबाई रखता है जो `pattern[0..i]` का suffix भी है — यह बताता है कि mismatch पर KMP को कितना खिसकना है, दोबारा शुरू करने के बजाय।

```python
def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    lps = build_lps(pattern)
    matches, i, j = [], 0, 0
    while i < len(text):
        if text[i] == pattern[j]:
            i, j = i + 1, j + 1
            if j == len(pattern):
                matches.append(i - j)
                j = lps[j - 1]
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return matches
```

Output:

```
kmp_search('ababcabab', 'abab')  # [0, 5]
```

## Rabin-Karp एक नज़र में

**Rabin-Karp**, pattern और text की हर window को hash करता है, पहले hashes की तुलना करता है (**rolling hash** से `O(1)`) और केवल hash मिलने पर character-by-character जांचता है। **एक साथ कई patterns** खोजने में बेहतरीन।

## त्वरित जांच

KMP की complexity परखें।

**Quiz:** लंबाई m के pattern को लंबाई n के text में खोजने पर KMP की कुल time complexity है:

- [ ] O(n*m)
- [x] O(n + m)
- [ ] O(n log m)
- [ ] O(m^2)

*Answer:* O(n + m). LPS array O(m) में बनती है, और खोज खुद O(n) है क्योंकि text pointer कभी पीछे नहीं जाता।