API tools faq
paste
Advertisement
playerr17

Untitled

playerr17
Dec 28th, 2022
131
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.65 KB | None | 0 0
raw download clone embed print report
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize ("unroll-loops")
  3. #pragma GCC optimize ("fast-math")
  4. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <string>
  9. #include <cmath>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <ctime>
  14. #include <stack>
  15. #include <queue>
  16. #include <iomanip>
  17. #include <cstdlib>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <cstddef>
  21.  
  22. using namespace std;
  23. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  24. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define all(x) x.begin(),x.end()
  28. #define sz(a) ((int)((a).size()))
  29. const int INF = 1e9+1;
  30. const long long MOD = 1e9+7;
  31. typedef long long ll;
  32. typedef long double ld;
  33.  
  34. ll p1[100100], p2[100100], p3[100100], step[100100], s1[100100], s2[100100], s3[100100];
  35.  
  36. int res = INF, O[3][3];
  37.  
  38. ll get_hash1(int l , int r) {return l != 0 ? p1[r] - p1[l - 1] * step[r - l + 1] : p1[r];}
  39.  
  40. ll get_hash2(int l , int r) {return l != 0 ? p2[r] - p2[l - 1] * step[r - l + 1] : p2[r];}
  41.  
  42. ll get_hash3(int l , int r) {return l != 0 ? p3[r] - p3[l - 1] * step[r - l + 1] : p3[r];}
  43.  
  44. int32_t main()
  45. {
  46.     //freopen("river.in", "r", stdin);
  47.     //freopen("river.out", "w", stdout);
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     cout.tie(NULL);
  51.     string a, b, c;
  52.     cin >> a >> b >> c;
  53.     int as = (int)a.size(), bs = (int)b.size(), cs = (int)c.size();
  54.     int n = max(as, max(bs, cs));
  55.     step[0] = 1;
  56.     forn1(i, 1, n) step[i] = step[i - 1] * 31;
  57.     p1[0] = a[0] - 'a' + 1;
  58.     p2[0] = b[0] - 'a' + 1;
  59.     p3[0] = c[0] - 'a' + 1;
  60.     forn(i, 1, n){
  61.         if(i < as) p1[i] = p1[i - 1] * 31 + a[i] - 'a' + 1;
  62.         if(i < bs) p2[i] = p2[i - 1] * 31 + b[i] - 'a' + 1;
  63.         if(i < cs) p3[i] = p3[i - 1] * 31 + c[i] - 'a' + 1;
  64.     }
  65.     s1[as - 1] = a[as - 1] - 'a' + 1;
  66.     s2[bs - 1] = b[bs - 1] - 'a' + 1;
  67.     s3[cs - 1] = c[cs - 1] - 'a' + 1;
  68.     for(int i = n - 2; i >= 0; i--){
  69.         if(i < as - 1) s1[i] = s1[i + 1] + (a[i] - 'a' + 1) * step[as - i - 1];
  70.         if(i < bs - 1) s2[i] = s2[i + 1] + (b[i] - 'a' + 1) * step[bs - i - 1];
  71.         if(i < cs - 1) s3[i] = s3[i + 1] + (c[i] - 'a' + 1) * step[cs - i - 1];
  72.     }
  73.     for(int i = 0; i < min(as, bs); i++){
  74.         if(s1[(int)a.size() - 1 - i] == p2[i]) O[0][1] = i + 1;
  75.     }
  76.     for(int i = 0; i < min(as, bs); i++){
  77.         if(s2[(int)b.size() - 1 - i] == p1[i]) O[1][0] = i + 1;
  78.     }
  79.     for(int i = 0; i < min(as, cs); i++){
  80.         if(s1[(int)a.size() - 1 - i] == p3[i]) O[0][2] = i + 1;
  81.     }
  82.     for(int i = 0; i < min(as, cs); i++){
  83.         if(s3[(int)c.size() - 1 - i] == p1[i]) O[2][0] = i + 1;
  84.     }
  85.     for(int i = 0; i < min(cs, bs); i++){
  86.         if(s3[(int)c.size() - 1 - i] == p2[i]) O[2][1] = i + 1;
  87.     }
  88.     for(int i = 0; i < min(cs, bs); i++){
  89.         if(s2[bs - 1 - i] == p3[i]) O[1][2] = i + 1;
  90.     }
  91.     int sum = as + bs + cs;
  92.     res = min(res, sum - O[0][1] - O[1][2]);
  93.     res = min(res, sum - O[0][2] - O[2][1]);
  94.     res = min(res, sum - O[2][0] - O[1][2]);
  95.     res = min(res, sum - O[0][2] - O[1][0]);
  96.     res = min(res, sum - O[2][0] - O[0][1]);
  97.     res = min(res, sum - O[2][1] - O[1][0]);
  98.     if(as >= bs && bs >= cs){
  99.         bool c1 = 0, c2 = 0, c3 = 0;
  100.         for(int i = 0; i + bs - 1 < as; i++){
  101.             if(p2[bs - 1] == get_hash1(i, i + bs - 1)){
  102.                 c1 = 1;
  103.                 break;
  104.             }
  105.         }
  106.         for(int i = 0; i + cs - 1 < as; i++){
  107.             if(p3[cs - 1] == get_hash1(i, i + cs - 1)){
  108.                 c3 = 1;
  109.                 break;
  110.             }
  111.         }
  112.         for(int i = 0; i + cs - 1 < bs; i++){
  113.             if(p3[cs - 1] == get_hash2(i, i + cs - 1)){
  114.                 c2 = 1;
  115.                 break;
  116.             }
  117.         }
  118.         if(c1 && c2) res = as;
  119.         else if(c1){
  120.             res = min(res, as + cs - O[0][2]);
  121.             res = min(res, as + cs - O[2][0]);
  122.         }
  123.         else if(c2 || c3){
  124.             res = min(res, as + bs - O[0][1]);
  125.             res = min(res, as + bs - O[1][0]);
  126.         }
  127.     } else if(as >= cs && cs >= bs){
  128.         bool c1 = 0, c2 = 0, c3 = 0;
  129.         for(int i = 0; i + cs - 1 < as; i++){
  130.             if(p3[cs - 1] == get_hash1(i, i + cs - 1)){
  131.                 c1 = 1;
  132.                 break;
  133.             }
  134.         }
  135.         for(int i = 0; i + bs - 1 < as; i++){
  136.             if(p2[bs - 1] == get_hash1(i, i + bs - 1)){
  137.                 c3 = 1;
  138.                 break;
  139.             }
  140.         }
  141.         for(int i = 0; i + bs - 1 < cs; i++){
  142.             if(p2[bs - 1] == get_hash3(i, i + bs - 1)){
  143.                 c2 = 1;
  144.                 break;
  145.             }
  146.         }
  147.         if(c1 && c2) res = as;
  148.         else if(c1){
  149.             res = min(res, as + bs - O[0][1]);
  150.             res = min(res, as + bs - O[1][0]);
  151.         }
  152.         else if(c3 || c2){
  153.             res = min(res, as + cs - O[0][2]);
  154.             res = min(res, as + cs - O[2][0]);
  155.         }
  156.     } else if(bs >= as && as >= cs){
  157.         bool c1 = 0, c2 = 0, c3 = 0;
  158.         for(int i = 0; i + as - 1 < bs; i++){
  159.             if(p1[as - 1] == get_hash2(i, i + as - 1)){
  160.                 c1 = 1;
  161.                 break;
  162.             }
  163.         }
  164.         for(int i = 0; i + cs - 1 < bs; i++){
  165.             if(p3[cs - 1] == get_hash2(i, i + cs - 1)){
  166.                 c3 = 1;
  167.                 break;
  168.             }
  169.         }
  170.         for(int i = 0; i + cs - 1 < as; i++){
  171.             if(p3[cs - 1] == get_hash1(i, i + cs - 1)){
  172.                 c2 = 1;
  173.                 break;
  174.             }
  175.         }
  176.         if(c1 && c2) res = bs;
  177.         else if(c1){
  178.             res = min(res, bs + cs - O[1][2]);
  179.             res = min(res, bs + cs - O[2][1]);
  180.         }
  181.         else if(c2 || c3){
  182.             res = min(res, bs + as - O[1][0]);
  183.             res = min(res, bs + as - O[0][1]);
  184.         }
  185.     } else if(bs >= cs && cs >= as){
  186.         bool c1 = 0, c2 = 0, c3 = 0;
  187.         for(int i = 0; i + as - 1 < bs; i++){
  188.             if(p1[as - 1] == get_hash2(i, i + as - 1)){
  189.                 c3 = 1;
  190.                 break;
  191.             }
  192.         }
  193.         for(int i = 0; i + cs - 1 < bs; i++){
  194.             if(p3[cs - 1] == get_hash2(i, i + cs - 1)){
  195.                 c1 = 1;
  196.                 break;
  197.             }
  198.         }
  199.         for(int i = 0; i + as - 1 < cs; i++){
  200.             if(p1[as - 1] == get_hash3(i, i + as - 1)){
  201.                 c2 = 1;
  202.                 break;
  203.             }
  204.         }
  205.         if(c1 && c2) res = bs;
  206.         else if(c1){
  207.             res = min(res, bs + as - O[1][0]);
  208.             res = min(res, bs + as - O[0][1]);
  209.         }
  210.         else if(c2 || c3){
  211.             res = min(res, bs + cs - O[1][2]);
  212.             res = min(res, bs + cs - O[2][1]);
  213.         }
  214.     } else if(cs >= as && as >= bs){
  215.         bool c1 = 0, c2 = 0, c3 = 0;
  216.         for(int i = 0; i + as - 1 < cs; i++){
  217.             if(p1[as - 1] == get_hash3(i, i + as - 1)){
  218.                 c1 = 1;
  219.                 break;
  220.             }
  221.         }
  222.         for(int i = 0; i + bs - 1 < cs; i++){
  223.             if(p2[bs - 1] == get_hash3(i, i + bs - 1)){
  224.                 c3 = 1;
  225.                 break;
  226.             }
  227.         }
  228.         for(int i = 0; i + bs - 1 < as; i++){
  229.             if(p2[bs - 1] == get_hash1(i, i + bs - 1)){
  230.                 c2 = 1;
  231.                 break;
  232.             }
  233.         }
  234.         if(c1 && c2) res = cs;
  235.         else if(c1){
  236.             res = min(res, bs + cs - O[1][2]);
  237.             res = min(res, bs + cs - O[2][1]);
  238.         }
  239.         else if(c2 || c3){
  240.             res = min(res, as + cs - O[2][0]);
  241.             res = min(res, as + cs - O[0][2]);
  242.         }
  243.     } else { // cs bs as
  244.         bool c1 = 0, c2 = 0, c3 = 0;
  245.         for(int i = 0; i + as - 1 < cs; i++){
  246.             if(p1[as - 1] == get_hash3(i, i + as - 1)){
  247.                 c3 = 1;
  248.                 break;
  249.             }
  250.         }
  251.         for(int i = 0; i + bs - 1 < cs; i++){
  252.             if(p2[bs - 1] == get_hash3(i, i + bs - 1)){
  253.                 c1 = 1;
  254.                 break;
  255.             }
  256.         }
  257.         for(int i = 0; i + as - 1 < bs; i++){
  258.             if(p1[as - 1] == get_hash2(i, i + as - 1)){
  259.                 c2 = 1;
  260.                 break;
  261.             }
  262.         }
  263.         if(c1 && c2) res = cs;
  264.         else if(c1){
  265.             res = min(res, as + cs - O[0][2]);
  266.             res = min(res, as + cs - O[2][0]);
  267.         }
  268.         else if(c2 || c3){
  269.             res = min(res, bs + cs - O[2][1]);
  270.             res = min(res, bs + cs - O[1][2]);
  271.         }
  272.     }
  273.     cout << res << endl;
  274.     return 0;
  275. }
  276.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!