Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <algorithm>
- #include <vector>
- using namespace std;
- struct DSU {
- int n;
- int *parent;
- int *rank;
- int *val;
- DSU(int n) {
- this->n = n;
- parent = new int[n];
- rank = new int[n];
- val = new int[n];
- for (int i = 0; i < n; i++) {
- parent[i] = i;
- rank[i] = 1;
- val[i] = i;
- }
- }
- ~DSU() {
- delete[] parent;
- delete[] rank;
- delete[] val;
- }
- int find_set(int v) {
- if (parent[v] == v) {
- return v;
- } else {
- return parent[v] = find_set(parent[v]);
- }
- }
- void unite(int v1, int v2) {
- int s1 = find_set(v1), s2 = find_set(v2);
- int resval = val[s2];
- if (rank[s1] < rank[s2]) {
- swap(s1, s2);
- }
- parent[s2] = s1;
- rank[s1] = max(rank[s1], rank[s2] + 1);
- val[s1] = resval;
- }
- };
- vector<int> z_function(string &str) {
- int len = str.length();
- vector<int> z(len, 0);
- for (int i = 1, l = 0, r = 0; i < len; i++) {
- if (r >= i) {
- z[i] = min(z[i - l], r - i + 1);
- }
- while (i + z[i] < len && str[i + z[i]] == str[z[i]]) {
- z[i]++;
- }
- if (i + z[i] - 1 > r) {
- l = i;
- r = i + z[i] - 1;
- }
- }
- return z;
- }
- string random_string(int len) {
- string result = "";
- for (int i = 0; i < len; i++) {
- result += 'a' + rand() % 26;
- }
- return result;
- }
- bool check(string &str1, string &str2, string &what, string &to) {
- int len1 = str1.length(), len2 = str2.length();
- int whatlen = what.length();
- string rep = "";
- for (int i = 0; i < len1; ) {
- if (i + whatlen < len1 && str1.substr(i, whatlen) == what) {
- rep += to;
- i += whatlen;
- } else {
- rep += str1[i];
- i++;
- }
- }
- return rep == str2;
- }
- string naive_solve(string &str1, string &str2) {
- int minsum = 1000000;
- int ansi1, anslen1, ansi2, anslen2;
- for (int i = 0; i < str1.length(); i++) {
- for (int len = 1; i + len <= str1.length(); len++) {
- for (int j = 0; j < str2.length(); j++) {
- for (int len2 = 1; j + len2 <= str2.length(); len2++) {
- if (check(str1, str2, str1.substr(i, len), str2.substr(j, len2))) {
- if (len + len2 < minsum) {
- minsum = len + len2;
- ansi1 = i;
- anslen1 = len;
- ansi2 = j;
- anslen2 = len2;
- }
- }
- }
- }
- }
- }
- return "s/" + str1.substr(ansi1, anslen1) + "/" + str2.substr(ansi2, anslen2) + "/g";
- }
- int main() {
- freopen("curiosity.in", "r", stdin);
- freopen("curiosity.out", "w", stdout);
- string str1, str2;
- getline(cin, str1);
- getline(cin, str2);
- //str1 = random_string(10);
- //str2 = random_string(11);
- int len1 = str1.length(), len2 = str2.length();
- vector< vector<int> > z2(len2);
- vector< vector<int> > z21(len2);
- for (int i = 0; i < len2; i++) {
- string str = str2.substr(i, len2 - i) + "#" + str2;
- z2[i] = z_function(str);
- str = str2.substr(i, len2 - i) + "#" + str1;
- z21[i] = z_function(str);
- }
- int bestlen = 1000000;
- int i1 = -1, leni1 = -1, i2 = -1, leni2 = -1;
- for (int i = 0; i < len1; i++) {
- string str = str1.substr(i, len1 - i) + "#" + str1;
- //cerr << str << endl;
- vector<int> z = z_function(str);
- vector< pair<int, int> > zvals(len1);
- for (int j = 0; j < len1; j++) {
- zvals[j] = make_pair(z[len1 - i + 1 + j], j);
- }
- sort(zvals.begin(), zvals.end());
- DSU dsu(len1 + 1);
- for (int len = 1, pos = 0; len <= len1; len++) {
- //cerr << i << " " << len << endl;
- while (pos < len1 && zvals[pos].first < len) {
- dsu.unite(zvals[pos].second, zvals[pos].second + 1);
- pos++;
- }
- int curpos = 0;
- vector<int> positions;
- while (curpos < len1) {
- int found = dsu.val[dsu.find_set(curpos)];
- if (found < len1) {
- positions.push_back(found);
- curpos = found + len;
- } else {
- curpos = len1;
- }
- }
- int occ = positions.size();
- if (occ == 0 || len2 < len1 - len * occ || (len2 - (len1 - len * occ)) % occ != 0) {
- continue;
- }
- int lenc = (len2 - (len1 - len * occ)) / occ;
- if (z21[0][len2 + 1 + 0] < positions[0]) {
- continue;
- }
- int prevend = positions[0] + lenc;
- for (int i = 1; i < occ; i++) {
- int pref = positions[0];
- int plen = len2 - pref;
- int p2 = positions[i] + (lenc - len) * i;
- if (p2 < len2 && z2[pref][plen + 1 + p2] < lenc || p2 == len2 && lenc > 0 || p2 > len2) {
- goto endi;
- }
- }
- for (int i = 0; i < occ; i++) {
- int opos1 = positions[i] + len;
- int opos2 = positions[i] + (lenc - len) * i + lenc;
- int lenb = i + 1 < occ ? positions[i + 1] - opos1 : len1 - opos1;
- if (opos2 < len2 && z21[opos2][len2 - opos2 + 1 + opos1] < lenb) {
- goto endi;
- }
- }
- if (len + lenc < bestlen) {
- bestlen = len + lenc;
- i1 = positions[0];
- leni1 = len;
- i2 = positions[0];
- leni2 = lenc;
- }
- endi:;
- }
- }
- //string ans1 = "s/" + str1.substr(i1, leni1) + "/" + str2.substr(i2, leni2) + "/g";
- cout << "s/" << str1.substr(i1, leni1) << "/" << str2.substr(i2, leni2) << "/g" << endl;
- //cout << naive_solve(str1, str2) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement