fork download
copy 
  1. /*
  2. --------------------------------DO NOT COPY I REQUEST YOU PLEASE--------------------------
  3.  
  4. AUTHOR : Chandan Agrawal
  5. College : Poornima College of Engg. jaipur, Raj
  6. Mail : chandanagrawal23@gmail.com
  7.  
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 100050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli long int
  20.  
  21. #define pb emplace_back
  22. #define INF 100000000000
  23. #define mod 1000000007
  24. #define MOD 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define loop(i,n) for (lli i = 0; i < n; i++)
  37. #define loopitr(xt,vec) for (auto xt : vec)
  38. #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  39. #define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
  40. #define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
  41. #define itr :: iterator it
  42. #define WL(t) while(t --)
  43.  
  44. #define all(v) v.begin(),v.end()
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50. #define vi vector<lli>
  51. #define seti set<lli>
  52. #define pii pair<lli,lli>
  53.  
  54. #define gcd(a,b) __gcd((a),(b))
  55. #define lcm(a,b) (a/gcd(a,b))*b
  56. #define abs(x) ((x < 0)?-(x):x)
  57.  
  58. template <typename T>
  59. void print(T x){cout<<x<<endl;}
  60. template <typename T1, typename T2>
  61. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  62. template <typename T1, typename T2,typename T3>
  63. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  64.  
  65. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  66. #define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.push_back(x);}
  67.  
  68. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  69. #define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  70. #define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
  71.  
  72. #define FD(N) fixed<<setprecision(N)
  73.  
  74. #define endl '\n'
  75.  
  76. #define deb(x) cout<<#x<<" "<<x<<endl;
  77.  
  78. /*
  79. ifstream cinn("i3.txt");
  80. ofstream coutt("o3.txt");
  81. */
  82.  
  83.  
  84. bool isvowel(char v) { return (0x208222>>(v&0x1f))&1; }
  85.  
  86. lli mceil(lli a,lli b){
  87.     if(a%b==0) return(a/b);
  88.     else return(a/b  +1);
  89. }
  90. lli mfloor(lli a,lli b){
  91.     return(a/b);
  92. }
  93.  
  94. ll modmul(ll a, ll b) {
  95.     return ((a%mod) * (b%mod)) % mod;
  96. }
  97.  
  98. ll modadd(ll a , ll b){
  99.     return((a%mod)+(b%mod)+mod)%mod;
  100. }
  101.  
  102. ll modsub(ll a , ll b){
  103.     return((a%mod) - (b%mod) + mod)%mod;
  104. }
  105.  
  106. lli fastexpo(lli a,lli b){
  107.     a = a%mod;
  108.     lli ans=1;
  109.     while(b){
  110.         if(b&1)
  111.             ans=(ans*1ll*a)%mod;
  112.         a=(a*1ll*a)%mod;
  113.         b=b/2;
  114.         }
  115.     return ans;
  116.  }
  117.  
  118.  /* -----------------------------------------------------HASHING-------------------------------------------------------------------*/
  119. /*
  120. some key points -
  121. 1. Use (long int) to remove TLE or Memory Limit issue
  122. 2. If still Wrong answer then may be collision occur , use p as bigger prime no. p : [31,53,107,209,4793]
  123. 3. use mod either 1e9+7
  124. 4 .If it still shows WA then surely collision occurs use Double Hashing
  125.    Double Hashing -
  126.         Make Prehash Array using two different p and mod so chances of collision is less
  127. 5. use pass by reference always
  128.  
  129.  
  130. */
  131.  
  132.  
  133. #define maxlen 100005 //maximum length of string
  134. lli pow_p[maxlen]; // p^i %m
  135. lli p_inv[maxlen]; // this is inverse_Mod(p^i) basically p^(-n) =  [p^(-1) ]^n so calculate just p^(-1) and caluclate power
  136.                // like inversemod(p^(-2)) = p^(-1) * p^(-1)
  137. void init(lli p)
  138. {
  139.     pow_p[0]=1;
  140.     p_inv[0]=1;
  141.     lli pinv = fastexpo(p,mod-2);
  142.     for(lli i=1;i<maxlen;i++)
  143.     {
  144.         pow_p[i] = modmul(pow_p[i-1],p);
  145.         p_inv[i] = modmul(p_inv[i-1],pinv);
  146.     }
  147. }
  148.  
  149. struct Hash{
  150.         // 0 based indexing
  151.         lli prehash[maxlen];
  152.         // hash(s) = sigma(i=0 to n-1) s[i]*p^(i)
  153.         // a->1 , b->2 , c->3 and so on
  154.  
  155.  
  156.  
  157.  
  158.         void precomputehash(string &s,lli p){ //p can be any prime 19 , 31, 53,107 ...
  159.  
  160.             prehash[0]=(s[0]-'a')+1;
  161.             for (lli i=1;i<s.size();i++) {
  162.                 prehash[i]= modadd(prehash[i-1] , modmul((s[i]-'a'+1),pow_p[i]));
  163.             }
  164.         }
  165.  
  166.         // hash[l..r] = ((hash[upto r] - hash[upto (l-1)] ) / P^l) % mod = ((hash[upto r] - hash[upto (l-1)] ) * modinv(P^l) )%mod
  167.         lli gethash(lli l, lli r){
  168.             if(l==0)
  169.                 return(prehash[r]%mod);
  170.             else{
  171.                 lli ans = modsub(prehash[r],prehash[l-1]);
  172.                 ans = modmul(ans, p_inv[l]);
  173.                 return ans;
  174.             }
  175.         }
  176.  
  177.         // hash value of all string means hash[0..(n-1)] // 0 based indexing
  178.         lli totalhash(string &s){
  179.             return(prehash[sz(s)-1]%mod);
  180.         }
  181. };
  182.  
  183. /* -----------------------------------------------------HASHING-------------------------------------------------------------------*/
  184.  
  185. lli cnt_overlap(string &aage , string &piche , Hash &obj_aage , Hash &obj_piche)
  186. {
  187.  lli cnt=0, f=0;
  188.  
  189.  lli i=sz(aage)-1; //for aage
  190.  lli j=0; // for piche
  191.  
  192.  lli len_aage = sz(aage);
  193.  lli len_piche = sz(piche);
  194.  
  195.  while(i>=0 and j<len_piche)
  196.  {
  197.      if(obj_aage.gethash(i,len_aage-1) == obj_piche.gethash(0,j) ){
  198.             cnt=j;
  199.             f=1;
  200.      }
  201.      i--;
  202.      j++;
  203. //     cnt++;
  204.  }
  205.  if(f)
  206.     return cnt+1;
  207.  return 0;
  208. }
  209.  
  210.  
  211.  
  212. int main(){
  213. fastio
  214. lli t=1;
  215. init(53);
  216. //cin>>t;
  217. while(t--) {
  218.     string a,b,c;
  219.     cin>>a>>b>>c;
  220.  
  221.     lli sza = sz(a);
  222.     lli szb = sz(b);
  223.     lli szc = sz(c);
  224.  
  225.     Hash obj_a , obj_b , obj_c;
  226.  
  227.     obj_a.precomputehash(a,53);
  228.  
  229.     obj_b.precomputehash(b,53);
  230.  
  231.     obj_c.precomputehash(c,53);
  232.  
  233.     lli diff;
  234.  
  235.     lli total = 0 , ans = INF;
  236.  
  237. // - -- - - - -- - -  - - - - - --- - - - - - - - - - - -
  238.  
  239.     //a+b+c
  240.  
  241.     total=0;
  242.     diff = sza+szb-cnt_overlap(a,b,obj_a,obj_b);
  243.     //print(diff);
  244.     total+=diff;
  245.     diff = szc - cnt_overlap(b,c,obj_b,obj_c);
  246.     //print(diff);
  247.     total+=diff;
  248.     ans = min(ans ,total);
  249.  
  250.  
  251.  
  252.     //a+c+b
  253.  
  254.     total=0;
  255.     diff = sza+szc - cnt_overlap(a,c,obj_a,obj_c);
  256.    // print(diff);
  257.     total+=diff;
  258.     diff = szb - cnt_overlap(c,b,obj_c,obj_b);
  259.     //print(diff);
  260.     total+=diff;
  261.     ans = min(ans ,total);
  262.  
  263.  
  264.     //b+a+c
  265.  
  266.     total=0;
  267.     diff = szb+sza - cnt_overlap(b,a,obj_b,obj_a);
  268.     total+=diff;
  269.     diff = szc - cnt_overlap(a,c,obj_a,obj_c);
  270.     total+=diff;
  271.     ans = min(ans ,total);
  272.  
  273.     //b+c+a
  274.  
  275.     total=0;
  276.     diff = szb+szc - cnt_overlap(b,c,obj_b,obj_c);
  277.     total+=diff;
  278.     diff = sza - cnt_overlap(c,a,obj_c,obj_a);
  279.     total+=diff;
  280.     ans = min(ans ,total);
  281.  
  282.  
  283.     //c+a+b
  284.  
  285.     total=0;
  286.     diff = szc+sza - cnt_overlap(c,a,obj_c,obj_a);
  287.     total+=diff;
  288.     diff = szb - cnt_overlap(a,b,obj_a,obj_b);
  289.     total+=diff;
  290.     ans = min(ans ,total);
  291.  
  292.  
  293.  
  294.     //c+b+a
  295.  
  296.     total=0;
  297.     diff = szc+szb - cnt_overlap(c,b,obj_c,obj_b);
  298.     total+=diff;
  299.     diff = sza - cnt_overlap(b,a,obj_b,obj_a);
  300.     total+=diff;
  301.     ans = min(ans ,total);
  302.  
  303. // --- -- -- - -- - - - ---- -- - - - - - -- - - -    
  304.  
  305.     print(ans);
  306.  
  307.  
  308.   }
  309. return 0;
  310. }
  311.  
Success #stdin #stdout 0s 5256KB
comments (?)
stdin
copy 
rdtevvmiqmfgvafkdypxjthzhfsbavmhgkavkfonscaokdxoscenpxrc

ijbvueenzsmgkmkrskjspvfchwkqdglkxnrdtevvmiqmfgvafkdypxjthz

kqdglkxnrdtevvmiqmfgvafkdypxjthzhfsbavmhgkavkfonscaokdxoscenpxrcivydtkrxjy
stdout
copy 
156
https://ideone.com/vYSd7G
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!