Purva09/algorithm-battlefield

1"""String Matching Algorithms"""2 3 4def naive_search(text, pattern):5    """Naive String Search - Brute force search"""6    occurrences = []7    for i in range(len(text) - len(pattern) + 1):8        if text[i:i + len(pattern)] == pattern:9            occurrences.append(i)10    return occurrences11 12 13def kmp_search(text, pattern):14    """KMP (Knuth-Morris-Pratt) Search - Uses failure function"""15    16    def build_failure_function(pattern):17        m = len(pattern)18        failure = [0] * m19        j = 020        21        for i in range(1, m):22            while j > 0 and pattern[i] != pattern[j]:23                j = failure[j - 1]24            25            if pattern[i] == pattern[j]:26                j += 127            28            failure[i] = j29        30        return failure31    32    n = len(text)33    m = len(pattern)34    failure = build_failure_function(pattern)35    occurrences = []36    j = 037    38    for i in range(n):39        while j > 0 and text[i] != pattern[j]:40            j = failure[j - 1]41        42        if text[i] == pattern[j]:43            j += 144        45        if j == m:46            occurrences.append(i - m + 1)47            j = failure[j - 1]48    49    return occurrences50 51 52def rabin_karp(text, pattern):53    """Rabin-Karp Search - Uses rolling hash"""54    d = 256  # Size of alphabet55    q = 101  # Prime number for modulo56    57    n = len(text)58    m = len(pattern)59    pattern_hash = 060    text_hash = 061    h = 162    occurrences = []63    64    # Calculate h = d^(m-1) % q65    for i in range(m - 1):66        h = (h * d) % q67    68    # Calculate pattern hash and first window69    for i in range(m):70        pattern_hash = (d * pattern_hash + ord(pattern[i])) % q71        text_hash = (d * text_hash + ord(text[i])) % q72    73    # Find occurrences74    for i in range(n - m + 1):75        if pattern_hash == text_hash:76            if text[i:i + m] == pattern:77                occurrences.append(i)78        79        if i < n - m:80            text_hash = (d * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % q81            if text_hash < 0:82                text_hash += q83    84    return occurrences85 86 87def boyer_moore(text, pattern):88    """Boyer-Moore Search - Starts from right to left"""89    90    def build_bad_char_table(pattern):91        bad_char = {}92        for i in range(len(pattern)):93            bad_char[pattern[i]] = max(bad_char.get(pattern[i], -1), i)94        return bad_char95    96    n = len(text)97    m = len(pattern)98    bad_char = build_bad_char_table(pattern)99    occurrences = []100    i = 0101    102    while i <= n - m:103        j = m - 1104        105        while j >= 0 and pattern[j] == text[i + j]:106            j -= 1107        108        if j < 0:109            occurrences.append(i)110            i += 1 if i + m < n else 1111        else:112            bad_char_shift = max(1, j - bad_char.get(text[i + j], -1))113            i += bad_char_shift114    115    return occurrences116