HASH VALUE (হ্যাস ভ্যুল্যু)

বিশাল কোন স্ট্রিং থেকে যে কোন সাইজের সাবস্ট্রিং বের করার জন্য হ্যাস ভ্যল্যু বেশ গুরুত্বপূর্ণ।
প্রবলেমটি সলভ করার জন্য একটি বেজ ভ্যল্যু ধরে নিতে হয়। ইংরেজী বর্ণ সংখ্যা 26 বিধায় বেজ ভ্যল্যুকে 26 থেকে বড় কোন প্রাইম নম্বার ধরে নিতে হবে। এর পর একটি মড ভ্যল্যু ধরে নিতে হবে। মড ভেল্যুর মান ইন্টিজার রেঞ্জের মধ্যে যত বড় প্রাইম নম্বার নেওয়া যায় ততই বেটার হবে।






একটি স্ট্রিং এবং একটি সাবস্টিং থাকবে। অ্যলগরিদম হচ্ছে স্ট্রিংটির মধ্যে সাবস্টিং আছে কি না সেটি পরিক্ষা করে দেখা। স্ট্রিং ম্যসিং অ্যলগরিদম ব্যবহার করা হলে যেখানে বিশাল কম্পিম্লিক্সিটি দরকার পড়ে সেখানে সংখ্যা পদ্ধতির আইডিয়া কাজে লাগিয়ে খুব সহজেই প্রবলেমটি সলভ করা সম্ভব।

প্রথমে মূল স্ট্রিংটাকে 26 থেকে বড় প্রাইম নম্বার 29কে বেজ ধরে নতুন সংখ্যা পদ্ধতিতে কনভার্ট করা যাক। কিন্তু সেটাকে অবশ্যই ইন্টিজার লিমিটের মধ্যে রাখতে হবে। কাজেেই ইন্টিজার রেঞ্জের শেষ দিকের একটি প্রাইম সংখ্যা 10^9+7 দিয়ে মড করতে থাকি। যত বড় মড ভ্যল্যু নেওয়া যাবে প্রোগ্রামটির সফলতা তত বেশি হবে। মড ভেল্যু 10^9+7 মানে হচ্ছে প্রোগ্রামটি ব্যর্থ হবার সম্ভাবনা 1/(10^9+7), যা প্রায় অসম্ভব।
এখন একটা অ্যরের সাহায্যে স্ট্রিংএর প্রত্যেক ক্যরেক্টারের স্থানীয় ভ্যালুকে সংখ্যা পদ্ধতির নিয়মে বেইজ ভ্যল্যু দিয়ে গুন করি, এবং নিদিষ্ট ক্যরেক্টারের ভ্যল্যু অ্যরেতে রাখি।
এবার আসা যাক সাবস্ট্রিং এ
সাবস্ট্রিং এর ক্ষেত্রেও ঠিক একই কাজ করব। সাবস্টিংকে 29 ডিজিটের সংখ্যাপদ্ধতিতে কনভার্ট করে ফেলি।

এখন মুল স্ট্রিং এর যে প্রথম থেকে শুরু করে সাবস্ট্রিংটি খুজতে থাকি।
 x=arr[i+l-1]-(arr[i-1]*(base^Sub string length)%mod;
প্রক্রিয়াটি সম্পান্ন করি।  যেকোন ক্ষ্রেত্রে x এর মান সাবস্টিং এর 29 ডিজিটের সংখ্যা পদ্ধতির মানের সমান হয় তাহলে বুঝতে হবে সাবস্ট্রিংটি মুল স্ট্রিং এর মধ্যে বিদ্যমান।





#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll arr[100000];
ll mod = 1e9+7;
ll base = 29;

int main()
{
    string s,t;
    cin>>s>>t;
    ll r=0;

    for(ll i=0; i<s.size(); i++){
        ll x = s[i]-'a';
        arr[i+1]=(arr[i]*base+x)%mod;
    }

    for(ll i=0; i<t.size(); i++){
        ll x = t[i]-'a';
        r=r*base+x;
        r=r%mod;
    }
    ll xx=1;
    ll l=t.size();
    for(ll i =1; i<=t.size(); i++){
        xx=(xx*base)%mod;
    }
    ll flag = 0;
    for(ll i=1; i<=s.size(); i++){
        ll x=arr[i+l-1]-(arr[i-1]*xx)%mod;
        if(x<0)x+=mod;
        if(x==r){
           cout<<"Matching...\n\n";
           flag++;
        }
    }
    if(flag==0){
        cout<<"Your Substring dose not exist in this string\n";
    }
    else{
        cout<<"Your Substring "<<flag<<" time exist in this string\n";
    }
    return 0;



    //cout<<r<<endl;
}