fork download
copy 
  1. //Try using Rabin Karp
  2. /*
  3. this code uses rabin karp +binary seach +hashing
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10. */
  11. #include <iostream>
  12. #include <vector>
  13. #include <string.h>
  14. #include <sstream>
  15. typedef  long long int lli;
  16. #define sz(a) lli((a).size())
  17. #define pb push_back
  18. #define all(c) (c).begin(),(c).end()
  19. #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
  20. #define present(c,x) ((c).find(x) != (c).end())
  21. #define cpresent(c,x) (find(all(c),x) != (c).end())
  22. #include <stdio.h>
  23. #include <set>
  24. #include <algorithm>
  25. #include <numeric>
  26. #include <stack>
  27. #include <list>
  28. #include <queue>
  29. #define MOD 1000000007
  30. #define MAX 250005
  31. #include <map>
  32. using namespace std;
  33. typedef vector<lli> vi;
  34. typedef vector<vi> vvi;
  35. typedef pair<lli,lli> ii;
  36. lli q=10000019;
  37. vector<lli> hasharr(q,-1);
  38. bool LCS(char *ans,char *inp1,char *inp2,lli n)
  39. {
  40. 	lli d=27;//ASCII Value in total
  41.  
  42. 	std::fill(hasharr.begin(), hasharr.end(), -1);
  43. 	lli M=n;
  44.   	lli N=strlen(inp1);
  45.   	lli n2=strlen(inp2);
  46.   	lli p=0;
  47.   	lli t=0;
  48.   	lli h=1;
  49.   	for(lli i=0;i<M-1;i++)
  50.    		h=(h%q*d%q)%q;
  51.    	for(lli i=0;i<M;i++)
  52.    	{ 	p=(d*p%q+inp2[i]%q)%q;
  53.      	t=(d*t%q+inp1[i]%q)%q;
  54.    	}
  55. 	hasharr[t]=0;
  56.    for(lli i=0;i<=N-M;i++)
  57.    {
  58.  
  59.        if(i<N-M)
  60.        { t=((d*(t%q-(inp1[i]*h)%q ))%q+inp1[i+M]%q)%q;
  61.  
  62.          if(t<0)
  63.          	t+=q;
  64.         hasharr[t]=i+1;
  65.  
  66.  
  67.        }//cout<<"T hash is "<<t<<endl;
  68.        //m1[t]=i+1;
  69.    } 
  70.    lli flag=0;
  71.    lli ansind;
  72.    for(lli i=0;i<=n2-M;i++)
  73.    {//cout<<"p hash is "<<p<<endl;
  74. 	 if(hasharr[p]!=-1)
  75.     	    {
  76.     	     ansind=hasharr[p];
  77.         	 flag=1;
  78.     		 break;
  79.  
  80.  
  81.             }
  82.  
  83.        if(i<n2-M)
  84.             { p=((d*(p%q-(inp2[i]*h)%q ))%q+inp2[i+M]%q)%q;
  85.  
  86.               if(p<0)
  87.                p=p+q;
  88.        // cout<<"\n\n"<<inp1[i]<<" "<<inp1[i+M]<<endl;
  89.             }
  90.        if(hasharr[p]!=-1)
  91.         {	ansind=hasharr[p];
  92.         	flag=1;
  93.         	break;
  94.  
  95.  
  96.         }
  97.  
  98.        //m1[t]=i+1;
  99.    }
  100.    for(lli i=ansind;i<ansind+M and flag==1;i++)
  101.    {
  102.    	ans[i-ansind]=inp1[i];
  103.  
  104.    }
  105.    if(flag==1)
  106.     {//cout<<endl<<"returning true for M is "<<M<<endl;
  107. 	return true;
  108.     }
  109. return false;
  110. }
  111. lli calculate(char *ans,char *inp1,char *inp2)
  112. { lli lo=1;
  113.   lli hi=strlen(inp2);
  114.   lli  middle;
  115.   lli flag=0;
  116.   while(lo<=hi)
  117.   { 
  118.  	if(lo==hi)
  119.  	{LCS(ans,inp1,inp2,lo);break;}
  120.   	middle=(lo+hi+1)/2;
  121.     //cout<<"middle is "<<middle<<endl;
  122.     if(LCS(ans,inp1,inp2,middle)==true)
  123.     { //cout<<"true at "<<middle<<endl;
  124.     	lo=middle; 
  125.     }
  126.     else
  127.    {//cout<<"not valid"<<endl;
  128.     	hi=middle-1;
  129.    }
  130.  
  131.   }
  132.   //cout<< "ans in calfunc "<<ans<<endl;
  133.  if(LCS(ans,inp1,inp2,lo))
  134.   {
  135.     return  lo;
  136.   }
  137.   else
  138.     return -1;
  139.  
  140.  
  141. }
  142. int main()
  143. { char *inp1=new char[250005];
  144.   char *inp2=new char[250005];
  145.   cin>>inp1>>inp2;
  146.   char *ans=new char[250005];
  147.   lli n=calculate(ans,inp1,inp2);
  148.   if(n!=-1)
  149.   {// cout<<"ans\n";
  150.   cout<<ans<<endl;
  151.     cout<<n<<endl;
  152.  
  153.  
  154.   }
  155.   else
  156.   cout<<0<<endl;
  157.  return 0;
  158. }
Success #stdin #stdout 0.03s 15984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VIKzEI
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!