Here’s the link to the problem:https://www.spoj.com/problems/ADAPHOTO/
Here,s the link to the solution i submitted:https://www.spoj.com/status/ADAPHOTO,sourav_suku
Id-26086255
#include<bits/stdc++.h>
#define m 100000007
#define pr 53
using namespace std;
void hashs(string s,vector &hs){
for(int i=1;i<hs.size();i++){
hs[i]=((hs[i-1]*pr)%m+s[i-1])%m;
}
}
int main(){
//int n;
//scanf("%d",n);
string f,s;
char po1[1000000],to[1000000];
scanf("%s %s",po1,to);
int tl=strlen(to),pl=strlen(po1);
int maxi=max(tl,pl);
int mini=min(tl,pl);
for(int i=0;i<tl;i++){
s.push_back(to[i]);
}
for(int i=0;i<pl;i++){
f.push_back(po1[i]);
}
vector<long long int> po(1000001);
po[0]=1;
for(int i=1;i<po.size();i++){
po[i]=(po[i-1]*pr)%m;
}
vector<long long > hf(f.size()+1),hs(s.size()+1);
hf[0]=0;
hs[0]=0;
hashs(f,hf);
hashs(s,hs);
//for(int i=0;i<hf.size();i++){
// cout<<hf[i]<<"\n";
//}
vector<long long> fc,sc;
long long int low=1,high,mid;
long long int l,sh;
long long temp;
if(f.size()>s.size())
{
high=s.size();
l=high;
sh=f.size();
}
else
{
high=f.size();
l=high;
sh=s.size();
}
long long int min=0;
//int str,en;
while(low<=high){
int flag=0;
fc.clear();
mid=(high+low)/2;
for(int i=0;i<=l-mid;i++){
if(l==f.size())
temp=(hf[i+mid]-((hf[i]*po[mid])%m)+m)%m;
else
temp=(hs[i+mid]-((hs[i]*po[mid])%m)+m)%m;
/*if(low==high)
{
cout<<hf[i+mid]<<" "<<(hf[i]*po[mid])<<" "<<(hf[i+mid]+m)%m<<" ";
cout<<temp<<"\n";
}*/
fc.push_back(temp);
}
sort(fc.begin(),fc.end());
for(int i=0;i<=sh-mid;i++){
if(l==f.size())
temp=(hs[i+mid]-((hs[i]*po[mid])%m)+m)%m;
else
temp=(hf[i+mid]-((hf[i]*po[mid])%m)+m)%m;
//cout<<temp<<"\n";
//cout<<"\n";
/*if(i==1&&high==low){
cout<<hs[i+mid]<<" "<<hs[i]<<" "<<po[mid]<<" "<<hs[i]*po[mid]<<" "<<(hs[i]*po[mid])%m<<" "<<hs[i+mid]-((hs[i]*po[mid])%m)<<" ";
}*/
if(binary_search(fc.begin(),fc.end(),temp))
{
flag=1;
//str=i;
}
}
if(flag==1){
min=mid;
low=mid+1;
}
else{
high=mid-1;
}
}
/*for(int i=str;i<str+min;i++){
if(l==f.size())
cout<<s[i];
else
{
cout<<f[i];
}
}*/
cout<<min<<"\n";
}
I used a rolling hash array and using prefix sums and binary search i found the length of the maximum common substring.But still it’s giving wrong answer.Can anyone please help me by looking into my code.I checked corner cases and integer overflows.But still not working after that.