NSOqwq

题解 CF1473B 【String LCM】

Codeforces 1473 B 题解

提供一个非常“傻”的暴力方法,但可以通过本题(

思路

先找出A的所有可能的拆解方式(例如样例1的第一个字符串: baba = ba $\times 2$ = baba $\times 1$)

然后找出B的所有可能拆解方式(例如样例1的第二个字符串: ba = ba $\times 1$)

发现 ba 是公共的,所以结果就是 ba $\times \operatorname{lcm}(2, 1)$ = baba

所以程序思路如下:

  • 找出A的所有可能的拆解方式,存储下来(我用了 pair<string, int>
  • 找出B的所有可能拆解方式,也存下来
  • 枚举A和B的所有拆解方式,找出最长的公共拆解方式(即两个拆解方式拆出来的字符串是一样的)
  • 然后生成 String LCM
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
typedef std::pair<std::string, int> psi;
std::string a, b;
std::vector<psi> aRes;
std::vector<psi> bRes;
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
void parseA() { // 生成A的所有拆解
    aRes = std::vector<psi>();
    for (int i = 1; i <= a.length(); i += 1) {
        if (a.length() % i == 0) {
            int x = a.length() / i;
            std::string now, last;
            bool flag = true;
            for (int j = 0; j < a.length(); j += 1) {
                const int n = j + 1;
                now += a[j];
                if (n % x == 0) {
                    if (last != now && last != std::string()) {
                        flag = false;
                        break;
                    }
                    last = now;
                    now = std::string();
                }
            }
            if (flag) {
                aRes.push_back( std::make_pair(last, i) );
            }
        }
    }
}
void parseB() { // 生成B的所有拆解
    bRes = std::vector<psi>();
    for (int i = 1; i <= b.length(); i += 1) {
        if (b.length() % i == 0) {
            int x = b.length() / i;
            std::string now, last;
            bool flag = true;
            for (int j = 0; j < b.length(); j += 1) {
                const int n = j + 1;
                now += b[j];
                if (n % x == 0) {
                    if (last != now && last != std::string() ) {
                        flag = false;
                        break;
                    }
                    last = now;
                    now = std::string();
                }
            }
            if (flag) {
                bRes.push_back( std::make_pair(last, i) );
            }
        }
    }
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        std::cin >> a >> b;
        parseA();
        parseB();
        bool flag = false;
        for (auto i : aRes) {
            for (auto b : bRes) { // 枚举所有拆解方式
                if (i.first == b.first) { // 如果是公共的连续子串
                    int _gcd = gcd(i.second, b.second);
                    int lcm = i.second * b.second / _gcd; // 生成String LCM并输出
                    for (int j = 1; j <= lcm; j += 1) std::cout << i.first;
                    printf("\n");
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (!flag) printf("-1\n");
    }
    return 0;
}

2021-01-23 11:12:33 in 题解