String Matching

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 को कितना खिसकना है, दोबारा शुरू करने के बजाय।

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 परखें।

त्वरित जाँच: लंबाई m के pattern को लंबाई n के text में खोजने पर KMP की कुल time complexity है:

• O(n*m)
• O(n + m)
• O(n log m)
• O(m^2)