রোলিং হ্যাশ বাস্তবায়নের জন্য C++ প্রোগ্রাম

রোলিং হ্যাশ হল একটি হ্যাশ ফাংশন যেখানে ইনপুট একটি উইন্ডোতে হ্যাশ করা হয় যা ইনপুটের মধ্য দিয়ে চলে।

রবিন-কার্প হল রোলিং হ্যাশের জনপ্রিয় প্রয়োগ। Rabin এবং Karp দ্বারা প্রস্তাবিত রোলিং হ্যাশ ফাংশন একটি পূর্ণসংখ্যা মান গণনা করে। একটি স্ট্রিংয়ের জন্য পূর্ণসংখ্যার মান হল একটি স্ট্রিংয়ের সাংখ্যিক মান।

রবিন-কার্প স্ট্রিং অনুসন্ধান অ্যালগরিদম প্রায়ই একটি খুব সাধারণ রোলিং হ্যাশ ফাংশন ব্যবহার করে ব্যাখ্যা করা হয় যা শুধুমাত্র গুণ এবং সংযোজন ব্যবহার করে −

H=c₁ a^k-1
 +c₂ a^k-2
 +….+ c_k a⁰
 .

যেখানে, a একটি ধ্রুবক এবং c₁ , c₂ ....c_k ইনপুট অক্ষর হয়. H-এর বিশাল মান ম্যানিপুলেট করার জন্য, mod n করা হয়।

অ্যালগরিদম

পূর্ণসংখ্যা ডেটাটাইপের একটি ধ্রুবক পরিবর্তনশীল P_B ঘোষণা করা শুরু করুন। P_B=227 শুরু করুন। পূর্ণসংখ্যা ডেটাটাইপের একটি ধ্রুবক পরিবর্তনশীল P_M ঘোষণা করুন। P_M=1000005 শুরু করুন। একটি হ্যাশ() ফাংশন ঘোষণা করুন প্যারামিটার হিসাবে একটি স্ট্রিং পাস করুন। পূর্ণসংখ্যা ডেটাটাইপের r ঘোষণা করুন। r =0. এর জন্য শুরু করুন (int i =0; i =n.size()) h2 -=power * hstack[i-n.size()] % P_M যদি (h2 <0) h2 +=P_M যদি ( i>=n.size()-1 &&h1 ==h2) রিটার্ন i - (n.size()-1); রিটার্ন -1; স্ট্রিং টাইপ s1 এবং s2 ঘোষণা করুন. প্রিন্ট করুন "ইনপুট স্ট্রিং লিখুন:" স্ট্রিং প্রবেশ করতে কল গেটলাইন (লাইন, s1)। প্রিন্ট করুন "এন্টার স্ট্রিং খুঁজে পেতে:" s2 এর জন্য ইনপুট নিন। if(rabin_karp(s2, s1) ==-1) প্রিন্ট করুন” স্ট্রিং পাওয়া যায়নি” অন্যথায় স্ট্রিং প্রিন্ট করুন। শেষ।

উদাহরণ কোড

#include #include Namespace ব্যবহার করে std;const int P_B=227;const int P_M =1000005;int hash(const string&s) { int r =0; জন্য (int i =0; i =n.size()) { h2 -=power * hstack[i-n.size()] % P_M; যদি (h2 <0) h2 +=P_M; } যদি (i>=n.size()-1 &&h1 ==h2) রিটার্ন i - (n.size()-1); } return -1;}int main() { স্ট্রিং s1, s2; cout<<"ইনপুট স্ট্রিং লিখুন:"; getline(cin, s1); cout<<"খুঁজতে স্ট্রিং লিখুন:"; cin>>s2; if(rabin_karp(s2, s1) ==-1) cout<<"স্ট্রিং পাওয়া যায়নি"< আউটপুট
 ইনপুট স্ট্রিং লিখুন:টিউটোরিয়ালসপয়েন্ট এন্টার স্ট্রিং খুঁজে বের করুন:aString a পাওয়া গেছে 6 অবস্থানে ইনপুট স্ট্রিং লিখুন:টিউটোরিয়ালপয়েন্ট এন্টার স্ট্রিং খুঁজে বের করুন:bString পাওয়া যায়নি