নেইভ স্ট্রিং ম্যাচিং ও রবিন-কার্প

def naive_match(text, pattern):
    # নেইভ O(nm): প্রতিটি সম্ভাব্য শুরুর পজিশনে ক্যারেক্টার-বাই-ক্যারেক্টার তুলনা
    n, m = len(text), len(pattern)
    positions = []
    if m == 0 or m > n:
        return positions
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions


def rabin_karp_match(text, pattern, base=256, mod=1_000_000_007):
    # রবিন-কার্প: পলিনোমিয়াল রোলিং হ্যাশ, O(1) প্রতি শিফটে আপডেট
    n, m = len(text), len(pattern)
    positions = []
    spurious_hits = []   # হ্যাশ মিলেছিল কিন্তু আসল ক্যারেক্টার মেলেনি -- এমন পজিশন
    if m == 0 or m > n:
        return positions, spurious_hits

    high_order = pow(base, m - 1, mod)   # b^(m-1) mod q, একবারই গণনা করা হয়

    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            # হ্যাশ মিলেছে -- কিন্তু এটি একটি সম্ভাব্য ম্যাচ মাত্র, নিশ্চিত নয়!
            # কলিশনের সম্ভাবনার কারণে আসল ক্যারেক্টারগুলো তুলনা করে ভেরিফাই করতেই হবে।
            if text[i:i + m] == pattern:
                positions.append(i)
            else:
                spurious_hits.append(i)
        if i < n - m:
            # রোলিং আপডেট: পুরনো ক্যারেক্টার বাদ, শিফট, নতুন ক্যারেক্টার যোগ -- সবই O(1)
            window_hash = (window_hash - ord(text[i]) * high_order) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash %= mod

    return positions, spurious_hits


tests = [
    ("abababab", "aba"),
    ("aaaaaaaa", "aa"),
    ("abcdefg", "xyz"),
    ("mississippi", "issi"),
    ("", "a"),
    ("abc", ""),
    ("abc", "abcd"),
    ("aaaa", "a"),
    ("thequickbrownfoxjumpsoverthelazydogthequickbrownfox", "thequickbrownfox"),
]

print(f"{'text':<54} | {'pattern':<18} | {'নেইভ':<16} | মিলেছে?")
all_ok = True
for text, pattern in tests:
    naive_pos = naive_match(text, pattern)
    rk_pos, spurious = rabin_karp_match(text, pattern)
    ok = (naive_pos == rk_pos)
    all_ok = all_ok and ok
    print(f"{text:<54} | {pattern:<18} | {str(naive_pos):<16} | {'হ্যাঁ' if ok else 'না -- BUG!'}")
    assert naive_pos == rk_pos, f"মিলছে না: {text!r}, {pattern!r}"

print("\nসব", len(tests), "টি টেস্ট কেসে নেইভ ও রবিন-কার্প পুরোপুরি একমত (assert পাস করেছে):", all_ok)

text = "abcdabcxabca"
pattern = "abca"

naive_pos = naive_match(text, pattern)
# ইচ্ছাকৃতভাবে খুব ছোট base=2, mod=2 -- বাস্তবে ব্যবহার করবেন না, শুধু কলিশন দেখানোর জন্য
rk_pos, spurious = rabin_karp_match(text, pattern, base=2, mod=2)

print("নেইভ ম্যাচ পজিশন:      ", naive_pos)
print("রবিন-কার্প ম্যাচ পজিশন:", rk_pos)
print("চূড়ান্ত ফলাফল মিলেছে?  ", naive_pos == rk_pos)

print(f"\nমোট {len(spurious)}টি স্পিউরিয়াস হিট (হ্যাশ মিলেছিল, ক্যারেক্টার মেলেনি):")
for i in spurious:
    window = text[i:i + len(pattern)]
    print(f"  পজিশন {i}: উইন্ডো {window!r} -- প্যাটার্ন {pattern!r}-এর সাথে হ্যাশ সমান, কিন্তু আসলে ভিন্ন স্ট্রিং")

assert naive_pos == rk_pos
print("\n-- ভেরিফিকেশন ধাপ (text[i:i+m] == pattern) থাকায় স্পিউরিয়াস হিটগুলো বাদ পড়েছে,")
print("   এবং চূড়ান্ত ফলাফল তবুও নেইভ বেসলাইনের সাথে সম্পূর্ণ সঠিক থেকেছে।")