AtCoder AGC 028 A - Two Abbreviations (茶色, 300 点)

そろそろまた競プロやっていくぞー！！！

問題へのリンク

問題概要

長さ n の文字列 S と長さ m の文字列 T が与えられる。以下の条件を満たす文字列 X があるかどうか判定し、あるならば X の長さ L として考えられる最小値を求めよ。
(以下において、n' = L/n, m' = L/m とする)

• L は n と m の公倍数である
• S は X[0], X[n'], X[2n'], ..., X[(n-1)n'] を順に並べてできる文字列
• T は X[0], X[m'], X[2m'], ..., X[(m-1)m'] を順に並べてできる文字列

考えたこと

いかにも最大公約数的な考え方が出て来そうな問題である。
とりあえず、X を n と m の最小公倍数に決め打ちしてみる。

例えば n = 6, m = 9, L = 18 としてみると、

• S は X[0], X[3], X[6], X[9], X[12], X[15]
• T は X[0], X[2], X[4], X[6], X[8], X[10], X[12], X[14], X[16]

である。よってそのような X が存在する条件とは

• S[0] = T[0]
• S[2] = T[3]
• S[4] = T[6]

が成立することである。これを一般化すると、n と m の最大公約数を g とすると、g 個の条件があって

• S[0] = T[0]
• S[n/g] = T[m/g]
• S[2n/g] = T[2m/g]
• ...
• S[(g-1)n/g] = T[(g-1)m/g]

が成立することが条件となる。特に、n と m が互いに素な場合には、S[0] = T[0] が成り立つかどうかだけ見ればいい。

そしてよくよく考えてみると、今は X の長さを n と m の最小公倍数に決めうちしたが、n と m の公倍数をどのように決めても同じ結論になる。

よって、

• 上記の条件を満たすとき、答えは n と m の最小公倍数
• 満たさないとき、答えは -1

となる。

#include <iostream>
#include <string>
using namespace std;

long long GCD(long long n, long long m) {
    return m ? GCD(m, n % m) : n;
}

int main() {
    long long n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    
    long long g = GCD(n, m);
    long long res = n / g * m;
    n /= g, m /= g;
    bool ok = true;
    for (long long i = 0; i < g; ++i) {
        if (s[i*n] != t[i*m]) ok = false;
    }
    if (ok) cout << res << endl;
    else cout << -1 << endl;
}