I was learning string hashing on spoj and they have suggested to solve this problem using naive approach and i tried but i am getting wrong ans and i am not able to figure out where i am making mistake ? Question link : https://www.spoj.com/problems/SUB_PROB/
My solution :
#include<bits/stdc++.h>
using namespace std;
const int p = 67;
const long long m = 1e9+9;
long long count_hash(string s)
{
long long hash_value = 0,pow_p = 1;
for(int i =0;i<s.size();i++)
{
if (s[i] >= 'a' && s[i] <= 'z')
hash_value = (hash_value + (s[i] - 'a' +1 )*pow_p)%m;
else if (s[i] >= 'A' && s[i] <= 'Z')
hash_value = (hash_value + (s[i] - 'A' +1 )*pow_p)%m;
else
hash_value = (hash_value + (s[i] - '1' +1 )*pow_p)%m;
pow_p = (pow_p*p)%m;
}
return hash_value;
}
void check_substring(string main_string,int n)
{
int X= main_string.size();
vector<long long> pow_p(X);
pow_p[0] = 1;
for(int i =1;i<X;i++)
pow_p[i] = (pow_p[i-1]*p)%m;
vector<long long> hash_main_string(X+1,0);
for(int i =0;i<X;i++)
{
if (main_string[i] >= 'a' && main_string[i] <= 'z')
hash_main_string[i+1] = (hash_main_string[i] + (main_string[i] - 'a' + 1) * pow_p[i])%m;
else if (main_string[i] >= 'A' && main_string[i] <= 'Z')
hash_main_string[i+1] = (hash_main_string[i] + (main_string[i] - 'A' + 1) * pow_p[i])%m;
else
hash_main_string[i+1] = (hash_main_string[i] + (main_string[i] - '1' + 1) * pow_p[i])%m;
}
/*for(int i =0;i<=X;i++)
{
cout<<hash_main_string[i]<<"\n";
}*/
while(n--)
{
string s;
cin>>s;
int hs = count_hash(s);
//cout<<"hs = "<<hs<<"\n";
int flag = 0;
for(int l = 1;l<=X-s.size()+1;l++)
{
long long cur_h = ((hash_main_string[l-1+s.size()]+m-hash_main_string[l-1])%m);
// cout<<cur_h<<"\n";
// cout<<"updated hs = "<<(hs*pow_p[l-1])%m<<"\n";
if (cur_h == ((hs*pow_p[l-1])%m))
{
flag = 1;
break;
}
}
if (flag == 1)
cout<<"Y\n";
else
{
cout<<"N\n";
}
}
}
int main()
{
string s;
while(cin>>s)
{
int n;
cin>>n;
check_substring(s,n);
}
return 0;
}
