Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const long long int mod = 1000000000000037;
- const long long int base = 127;
- long long int baza;
- long long int n,n1,n2;
- string s1,s2,s3;
- vector<long long int>h1,h2;
- ///----------------------------------------------
- void read()
- {
- cin>>n;
- cin>>s1>>s2>>s3;
- }
- ///----------------------------------------------
- void assign_hash(long long int i, long long int s, vector<long long int>&h, long long int e)
- {
- if(i==e)
- {
- h.push_back(s);
- return;
- }
- assign_hash(i+1,(s*base+s1[i])%mod,h,e);
- assign_hash(i+1,(s*base+s2[i])%mod,h,e);
- assign_hash(i+1,(s*base+s3[i])%mod,h,e);
- }
- ///----------------------------------------------
- void base_hash()
- {
- baza=base;
- for(int i=1;i<n2;i++)
- {
- baza=(baza*base)%mod;
- }
- for(int i=0; i<(int)h1.size(); i++)
- {
- __int128 h,b;
- h=h1[i];
- b=baza;
- h=(h*b)%mod;
- h1[i]=h;
- //cout<<h1[]
- }
- }
- ///----------------------------------------------
- long long int binary_sear4(long long int k)
- {
- long long int l=-1,r=h2.size(),ans=mod*2,m;
- while(l<=r)
- {
- //cout<<l<<" "<<r<<endl;
- m=(l+r)/2;
- if(k+h2[m]>=mod)
- {
- r=m-1;
- ans=h2[m];
- }
- else
- {
- l=m+1;
- }
- }
- return (ans+k)-mod;
- }
- ///----------------------------------------------
- void solve()
- {
- n1=n/2;
- n2=n-n1;
- assign_hash(0,0,h1,n1);
- assign_hash(n1,0,h2,n);
- base_hash();
- sort(h2.begin(),h2.end());
- long long int sum1,sum2,min_sum=1e18+5;
- for(int i=0; i<(int)h1.size(); i++)
- {
- //cout<<h1[i]<<" first hash "<<h2[0]<<endl;
- sum1=(h1[i]+h2[0])%mod;
- sum2=binary_sear4(h1[i]);
- //cout<<sum1<<" "<<sum2<<endl;
- min_sum=min(min_sum,min(sum1,sum2));
- //min_sum+=mod;
- //min_sum%=mod;
- }
- cout<<min_sum<<endl;
- }
- ///----------------------------------------------
- int main()
- {
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement