Rabin-Karp
রেবিন-কার্প
Text-এর প্রতিটা m-length window-র rolling hash বানিয়ে pattern-এর hash-এর সাথে মিলিয়ে দেখা string matching — গড়ে O(n+m), খারাপে O(nm)।
also: rabin karp, rolling hash, karp-rabin
Window এক ঘর সরালে পুরো hash নতুন করে না বানাতে হয় — এক update:
h_new = ((h_old - ord(text[i]) * high) * BASE + ord(text[i + m])) % MODHash মিললেই সত্যি মিল নয় — character-by-character verify লাগে; মিথ্যা positive-কে spurious hit বলে, ভালো modulus বাছলে বিরল।
Single pattern-এ KMP-র চেয়ে পার্থক্য কম; আসল শক্তি multi-pattern — একই text scan-এ kটা pattern-এর hash-set মেলানো যায়। Plagiarism detection, document similarity — এই কাজেই ব্যবহৃত।