Rabin karps sol

facebook
Tags: #<Tag:0x00007f243a85ee08>

#1

Comment body goes here.
bool check(const string A,const string B,int i)
{
for(int j=i;j<B.size()+i;j++)
{
if(A[j]!=B[j-i])
{
return false;
}
}
return true;
}
long long int has(const string B,int y,int f)
{ long long int l=0;
for(int i=f;i<y;i++)
{
l=l+(int(B[i])*pow(3,y-i-1));
}
return l;
}
int Solution::strStr(const string A, const string B) {
long long int l=has(B,B.size(),0);

//cout<< l<< endl;

if(A.size()<B.size())
{
    return -1;
}
   long long int s=has(A,B.size(),0);
if(l==s)
{
    if(check(A,B,0))
        {
            return 0;
        }
}
for(int i=B.size();i<A.size();i++)
{  s=((s-(int(A[i-B.size()])*pow(3,B.size()-1) ))*3) +int(A[i]);
       // s=has(A,i,i-B.size());
           //cout<< s<< endl;
    if(s==l)
    {
        if(check(A,B,i-B.size()+1))
        {
            return (i-B.size()+1);
         
        }
    }
}
return -1;

}