NHAY - A Needle in the Haystack - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : NHAY

👉 Hint : Standard Pattern Searching(Rabin–Karp(given below) or KMP)

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
 
ll power(ll a,ll n)
{
    if(n==0)
        return 1;
    ll x=power(a,n/2)%mod;
    x=(x*x)%mod;
    if(n%2==1)
        x=(x*a)%mod;
    return x;
}
 
ll po=power(256,mod);
int main()
{
    int t;
    ll hash[10000001];
    while(scanf("%d",&t)!=EOF)
    {
        string p,s;
        cin>>p;
        cin>>s;
        ll m=p.length();
        ll n=s.length();
        ll phash=0;
        for(ll i=0;i<m;i++)
            phash=(phash+(p[i]*power(256,m-i-1))%mod)%mod;
        hash[0]=0;
        for(ll i=0;i<m;i++)
        {
            hash[0]=(hash[0]+s[i]*power(256,m-i-1)%mod)%mod;
            if(hash[0]==phash)
                cout<<"0\n";
        }
        for(ll i=1;i<=n-m;i++)
        {
            hash[i]=(((hash[i-1]-(s[i-1]*power(256,m-1))%mod+mod)%mod*256)%mod+s[i+m-1])%mod;
            if(hash[i]==phash)
                cout<<i<<"\n";
        }
        cout<<"\n";
 
    }
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.