Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long int mod = 1000000000000037;
  4. const long long int base = 127;
  5. long long int baza;
  6. long long int n,n1,n2;
  7. string s1,s2,s3;
  8. vector<long long int>h1,h2;
  9. ///----------------------------------------------
  10. void read()
  11. {
  12. cin>>n;
  13. cin>>s1>>s2>>s3;
  14. }
  15. ///----------------------------------------------
  16. void assign_hash(long long int i, long long int s, vector<long long int>&h, long long int e)
  17. {
  18. if(i==e)
  19. {
  20. h.push_back(s);
  21. return;
  22. }
  23. assign_hash(i+1,(s*base+s1[i])%mod,h,e);
  24.  
  25. assign_hash(i+1,(s*base+s2[i])%mod,h,e);
  26.  
  27. assign_hash(i+1,(s*base+s3[i])%mod,h,e);
  28. }
  29. ///----------------------------------------------
  30. void base_hash()
  31. {
  32. baza=base;
  33. for(int i=1;i<n2;i++)
  34. {
  35. baza=(baza*base)%mod;
  36. }
  37. for(int i=0; i<(int)h1.size(); i++)
  38. {
  39. __int128 h,b;
  40. h=h1[i];
  41. b=baza;
  42. h=(h*b)%mod;
  43. h1[i]=h;
  44. //cout<<h1[]
  45. }
  46. }
  47. ///----------------------------------------------
  48. long long int binary_sear4(long long int k)
  49. {
  50. long long int l=-1,r=h2.size(),ans=mod*2,m;
  51. while(l<=r)
  52. {
  53. //cout<<l<<" "<<r<<endl;
  54. m=(l+r)/2;
  55. if(k+h2[m]>=mod)
  56. {
  57. r=m-1;
  58. ans=h2[m];
  59. }
  60. else
  61. {
  62. l=m+1;
  63. }
  64. }
  65. return (ans+k)-mod;
  66. }
  67. ///----------------------------------------------
  68. void solve()
  69. {
  70. n1=n/2;
  71. n2=n-n1;
  72. assign_hash(0,0,h1,n1);
  73. assign_hash(n1,0,h2,n);
  74. base_hash();
  75. sort(h2.begin(),h2.end());
  76. long long int sum1,sum2,min_sum=1e18+5;
  77. for(int i=0; i<(int)h1.size(); i++)
  78. {
  79. //cout<<h1[i]<<" first hash "<<h2[0]<<endl;
  80. sum1=(h1[i]+h2[0])%mod;
  81. sum2=binary_sear4(h1[i]);
  82.  
  83. //cout<<sum1<<" "<<sum2<<endl;
  84. min_sum=min(min_sum,min(sum1,sum2));
  85. //min_sum+=mod;
  86. //min_sum%=mod;
  87. }
  88. cout<<min_sum<<endl;
  89. }
  90. ///----------------------------------------------
  91. int main()
  92. {
  93. read();
  94. solve();
  95. return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement