String Algorithms — KMP, Rabin-Karp, suffix structures

লক্ষ্য: theory section-এর দুই algorithm-কে test-suite দিয়ে বাঁধা।

import random


def build_lps(pat: str) -> list[int]:
    """lps[i] = pat[:i+1]-এর longest proper prefix==suffix"""
    lps = [0] * len(pat)
    ln = 0
    for i in range(1, len(pat)):
        while ln and pat[i] != pat[ln]:
            ln = lps[ln - 1]
        if pat[i] == pat[ln]:
            ln += 1
        lps[i] = ln
    return lps


def print_lps_table(pat: str):
    lps = build_lps(pat)
    print(f"pat : {' '.join(pat)}")
    print(f"lps : {' '.join(map(str, lps))}")


def kmp_search(text: str, pat: str) -> list[int]:
    """সব occurrence (overlapping সহ) — Θ(n+m) guaranteed"""
    if not pat:
        return list(range(len(text) + 1))
    lps = build_lps(pat)
    hits, j = [], 0
    for k, ch in enumerate(text):
        while j and ch != pat[j]:
            j = lps[j - 1]           # pattern-এর memory — text পিছায় না
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            hits.append(k - j + 1)
            j = lps[j - 1]           # overlapping match: 'aa' in 'aaa' ×2
    return hits


def rabin_karp_search(text: str, pat: str, q=(1 << 61) - 1, b=256):
    """(hits, stats) — stats-এ hash-cmp আর true-verify আলাদা গোনা হয়"""
    n, m = len(text), len(pat)
    if not pat or m > n:
        return [], {'cmp': 0, 'verify': 0}
    bm, hp, ht = pow(b, m - 1, q), 0, 0
    for i in range(m):
        hp = (hp * b + ord(pat[i])) % q
        ht = (ht * b + ord(text[i])) % q
    stats = {'cmp': 0, 'verify': 0}
    hits = []
    for s in range(n - m + 1):
        stats['cmp'] += 1
        if ht == hp:
            stats['verify'] += 1
            if text[s:s + m] == pat:      # verify-on-match: hash≠proof
                hits.append(s)
        else:
            pass
        if s + m < n:
            ht = ((ht - ord(text[s]) * bm) * b + ord(text[s + m])) % q
    return hits, stats


if __name__ == '__main__':
    # ---------- LPS verification ----------
    for pat, want in [('ababc', [0, 0, 1, 2, 0]), ('aaaa', [0, 1, 2, 3]),
                      ('abcdabd', [0, 0, 0, 0, 1, 2, 0]),
                      ('aabaabaaa', [0, 1, 0, 1, 2, 3, 4, 5, 2])]:
        got = build_lps(pat)
        assert got == want, (pat, got)
    print_lps_table('abcdabd')

    # ---------- search correctness ----------
    assert kmp_search('ababcababcabc', 'ababc') == [0, 5]
    assert kmp_search('aaaa', 'aa') == [0, 1, 2]          # overlapping!
    assert kmp_search('hello', 'xyz') == []
    hits, st = rabin_karp_search('ababcababcabc', 'ababc')
    assert hits == [0, 5]
    print(f'rabin-karp stats: {st}')

    # ---------- fuzz vs oracle ----------
    rng = random.Random(7)
    trials = 500
    for _ in range(trials):
        t = ''.join(rng.choice('ab') for _ in range(rng.randint(0, 60)))
        p = ''.join(rng.choice('ab') for _ in range(rng.randint(1, 6)))
        oracle = [s for s in range(len(t) - len(p) + 1) if t[s:s + len(p)] == p]
        assert kmp_search(t, p) == oracle, (t, p)
        rk, _ = rabin_karp_search(t, p)
        assert rk == oracle, (t, p)
    print(f'fuzz: {trials} instances × (kmp+rabin-karp) vs oracle — ALL PASS')

প্রত্যাশিত output:

pat : a b c d a b d
lps : 0 0 0 1 2 0 1
rabin-karp stats: {'cmp': 9, 'verify': 2}
fuzz: 500 instances × (kmp+rabin-karp) vs oracle — ALL PASS

পড়ার বিষয়: cmp=13, verify=2 — দুইটা hash-hit-এর মধ্যে দুটোই true match (small q হলে false-positive-ও দেখতে পাবেন)। Binary-alphabet fuzz ইচ্ছাকৃত — dense self-similar strings-ই LPS fallback chain আর collision দুটোকেই stress করে।

নিজে বাড়ান:

১. Z-algorithm implement করে KMP-র সাথে cross-check করুন — একই occurrences, ভিন্ন machinery। ২. Small-q collision demo: q=101 নিয়ে adversarial text-এ verified-false count প্রিন্ট করুন — collision-এর বাস্তব মুখ। ৩. Aho-Corasick light: একাধিক pattern একসাথে trie+failure links — plagiarism checker-এর engine।