Advertisement
Guest User

Untitled

a guest
Oct 31st, 2013
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. struct DSU {
  9.  
  10.     int n;
  11.     int *parent;
  12.     int *rank;
  13.     int *val;
  14.  
  15.     DSU(int n) {
  16.         this->n = n;
  17.         parent = new int[n];
  18.         rank = new int[n];
  19.         val = new int[n];
  20.         for (int i = 0; i < n; i++) {
  21.             parent[i] = i;
  22.             rank[i] = 1;
  23.             val[i] = i;
  24.         }
  25.     }
  26.  
  27.     ~DSU() {
  28.         delete[] parent;
  29.         delete[] rank;
  30.         delete[] val;
  31.     }
  32.  
  33.     int find_set(int v) {
  34.         if (parent[v] == v) {
  35.             return v;
  36.         } else {
  37.             return parent[v] = find_set(parent[v]);
  38.         }
  39.     }
  40.  
  41.     void unite(int v1, int v2) {
  42.         int s1 = find_set(v1), s2 = find_set(v2);
  43.         int resval = val[s2];
  44.         if (rank[s1] < rank[s2]) {
  45.             swap(s1, s2);
  46.         }
  47.         parent[s2] = s1;
  48.         rank[s1] = max(rank[s1], rank[s2] + 1);
  49.         val[s1] = resval;
  50.     }
  51.  
  52. };
  53.  
  54. vector<int> z_function(string &str) {
  55.     int len = str.length();
  56.     vector<int> z(len, 0);
  57.     for (int i = 1, l = 0, r = 0; i < len; i++) {
  58.         if (r >= i) {
  59.             z[i] = min(z[i - l], r - i + 1);
  60.         }
  61.         while (i + z[i] < len && str[i + z[i]] == str[z[i]]) {
  62.             z[i]++;
  63.         }
  64.         if (i + z[i] - 1 > r) {
  65.             l = i;
  66.             r = i + z[i] - 1;
  67.         }
  68.     }
  69.     return z;
  70. }
  71.  
  72. string random_string(int len) {
  73.     string result = "";
  74.     for (int i = 0; i < len; i++) {
  75.         result += 'a' + rand() % 26;
  76.     }
  77.     return result;
  78. }
  79.  
  80. bool check(string &str1, string &str2, string &what, string &to) {
  81.     int len1 = str1.length(), len2 = str2.length();
  82.     int whatlen = what.length();
  83.     string rep = "";
  84.     for (int i = 0; i < len1; ) {
  85.         if (i + whatlen < len1 && str1.substr(i, whatlen) == what) {
  86.             rep += to;
  87.             i += whatlen;
  88.         } else {
  89.             rep += str1[i];
  90.             i++;
  91.         }
  92.     }
  93.     return rep == str2;
  94. }
  95.  
  96. string naive_solve(string &str1, string &str2) {
  97.     int minsum = 1000000;
  98.     int ansi1, anslen1, ansi2, anslen2;
  99.     for (int i = 0; i < str1.length(); i++) {
  100.         for (int len = 1; i + len <= str1.length(); len++) {
  101.             for (int j = 0; j < str2.length(); j++) {
  102.                 for (int len2 = 1; j + len2 <= str2.length(); len2++) {
  103.                     if (check(str1, str2, str1.substr(i, len), str2.substr(j, len2))) {
  104.                         if (len + len2 < minsum) {
  105.                             minsum = len + len2;
  106.                             ansi1 = i;
  107.                             anslen1 = len;
  108.                             ansi2 = j;
  109.                             anslen2 = len2;
  110.                         }
  111.                     }
  112.                 }
  113.             }
  114.         }
  115.     }
  116.     return "s/" + str1.substr(ansi1, anslen1) + "/" + str2.substr(ansi2, anslen2) + "/g";
  117. }
  118.  
  119. int main() {
  120.     freopen("curiosity.in", "r", stdin);
  121.     freopen("curiosity.out", "w", stdout);
  122.  
  123.     string str1, str2;
  124.     getline(cin, str1);
  125.     getline(cin, str2);
  126.     //str1 = random_string(10);
  127.     //str2 = random_string(11);
  128.    
  129.     int len1 = str1.length(), len2 = str2.length();
  130.  
  131.     vector< vector<int> > z2(len2);
  132.     vector< vector<int> > z21(len2);
  133.  
  134.     for (int i = 0; i < len2; i++) {
  135.         string str = str2.substr(i, len2 - i) + "#" + str2;
  136.         z2[i] = z_function(str);
  137.         str = str2.substr(i, len2 - i) + "#" + str1;
  138.         z21[i] = z_function(str);
  139.     }
  140.  
  141.     int bestlen = 1000000;
  142.     int i1 = -1, leni1 = -1, i2 = -1, leni2 = -1;
  143.  
  144.     for (int i = 0; i < len1; i++) {
  145.         string str = str1.substr(i, len1 - i) + "#" + str1;
  146.         //cerr << str << endl;
  147.         vector<int> z = z_function(str);
  148.         vector< pair<int, int> > zvals(len1);
  149.         for (int j = 0; j < len1; j++) {
  150.             zvals[j] = make_pair(z[len1 - i + 1 + j], j);
  151.         }
  152.         sort(zvals.begin(), zvals.end());
  153.         DSU dsu(len1 + 1);
  154.         for (int len = 1, pos = 0; len <= len1; len++) {
  155.             //cerr << i << " " << len << endl;
  156.             while (pos < len1 && zvals[pos].first < len) {
  157.                 dsu.unite(zvals[pos].second, zvals[pos].second + 1);
  158.                 pos++;
  159.             }
  160.             int curpos = 0;
  161.  
  162.             vector<int> positions;
  163.  
  164.             while (curpos < len1) {
  165.                 int found = dsu.val[dsu.find_set(curpos)];
  166.                 if (found < len1) {
  167.                     positions.push_back(found);
  168.                     curpos = found + len;
  169.                 } else {
  170.                     curpos = len1;
  171.                 }
  172.             }
  173.  
  174.             int occ = positions.size();
  175.  
  176.             if (occ == 0 || len2 < len1 - len * occ || (len2 - (len1 - len * occ)) % occ != 0) {
  177.                 continue;
  178.             }
  179.  
  180.             int lenc = (len2 - (len1 - len * occ)) / occ;
  181.  
  182.             if (z21[0][len2 + 1 + 0] < positions[0]) {
  183.                 continue;
  184.             }
  185.  
  186.             int prevend = positions[0] + lenc;
  187.  
  188.             for (int i = 1; i < occ; i++) {
  189.                 int pref = positions[0];
  190.                 int plen = len2 - pref;
  191.                 int p2 = positions[i] + (lenc - len) * i;
  192.                 if (p2 < len2 && z2[pref][plen + 1 + p2] < lenc || p2 == len2 && lenc > 0 || p2 > len2) {
  193.                     goto endi;
  194.                 }
  195.             }
  196.  
  197.             for (int i = 0; i < occ; i++) {
  198.                 int opos1 = positions[i] + len;
  199.                 int opos2 = positions[i] + (lenc - len) * i + lenc;
  200.                 int lenb = i + 1 < occ ? positions[i + 1] - opos1 : len1 - opos1;
  201.                 if (opos2 < len2 && z21[opos2][len2 - opos2 + 1 + opos1] < lenb) {
  202.                     goto endi;
  203.                 }
  204.             }
  205.            
  206.             if (len + lenc < bestlen) {
  207.                 bestlen = len + lenc;
  208.                 i1 = positions[0];
  209.                 leni1 = len;
  210.                 i2 = positions[0];
  211.                 leni2 = lenc;
  212.             }
  213.         endi:;
  214.         }
  215.     }
  216.  
  217.     //string ans1 = "s/" + str1.substr(i1, leni1) + "/" + str2.substr(i2, leni2) + "/g";
  218.  
  219.     cout << "s/" << str1.substr(i1, leni1) << "/" << str2.substr(i2, leni2) << "/g" << endl;
  220.     //cout << naive_solve(str1, str2) << endl;
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement