Rabin–Karp Rolling Hash Matching — Rabin–Karp hash பொருத்தம்

Rabin–Karp — நகரும் சாளர hash; pattern hash ஒப்பீடு; மோதல் — உண்மை சரம் சோதனை.

உண்மை உலகில் இது ஏன் முக்கியம்?

பிளேஜியரிசம் — rolling hash. உயிரியல் — k-mer.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

அடிப்படை B, mod M; புதிய char — பழைய நீக்கி, B பெருக்கி, புதிய சேர்த்து % M; hash சமம் — உறுதிப்படுத்தல்.

Pythonில் முயற்சி செய்வோம்

def rk_hash(s: str, base: int = 257, mod: int = 10**9 + 7) -> int:
    h = 0
    for c in s:
        h = (h * base + ord(c)) % mod
    return h


print(rk_hash("abc"), rk_hash("ab"))

அடிக்கடி நேரும் தவறுகள்

• பல தவறான சமம் — எப்போதும் verify.
• Unicode — சிறு int வரைபடம்.

முக்கியச் சுருக்கக் குறிப்புகள்

• பல pattern — RK வலிமை.
• ஒருமுறை — find/KMP எளிது.