AtCoder AGC028 A - Two Abbreviations (300点)

ちょっとだけ迷走した。
AtCoder Grand Contest 028のA。

概要

問題URL
A - Two Abbreviations

二つの文字列 $S$ (長さ $N$ ), $T$ (長さ $M$ )が与えられる。
文字列 $X$ (長さ $L$ )について、

$L$ は $N, M$ のどちらでも割り切れる
$X$ の $1, \frac L N+1, 2\times {\frac L N}+1, ..., (N-1)\times\frac L N+1$ 番目だけ抽出してくるとSと同じ
$X$ の $1, \frac L M+1, 2\times {\frac L M}+1, ..., (N-1)\times\frac L M+1$ 番目だけ抽出してくるとTと同じ

となる文字列 $X$ が存在するならばそのうちで最短のものの長さを、存在しないならば-1を出力せよ。

制約

$1\leq N, M\leq10^5$

解説

$S$ と $T$ を両方ともいい感じに同じ長さに引き伸ばして、場所がかぶったところの文字が全部同じになったらOKという感じです。 $2\times {\frac L N}+1$ とか言っていてわかりづらいですが、0-basedで考えると $\frac L N$ の整数倍というだけなので簡単です。
f:id:hewla:20181014000304p:plain
入出力例3の様子を画像にしてみました。見づらくてすみません>_<
かぶっているところが赤く塗られていますが、その部分が上の文字列 $S$ としたの文字列 $T$ で同じです。このように、場所のかぶったところが同じならその長さは条件を満たします。

まず、 $L$ は $N, M$ のどちらでも割り切れるので、 $L$ は一番小さくて $N, M$ の最小公倍数 $(LCM(N, M))$ で、必ず $LCM(N, M)$ の倍数です。この時場所がかぶっている文字は、 $N, M$ の最大公約数を $g = GCD(N, M)$ とすると、

文字列SではS[ $\frac {iN} g$ ], 文字列TではT[ $\frac {iM} g$ ] $(i = 0, 1, 2, ..., g-1)$

です。
さらに考えると、こうしてできた文字列で場所がかぶっている文字は、この文字列をいくら引きのばしても場所がかぶったままです。よって、 $L = LCM(N, M)$ でうまくいかない場合は、これを満たす文字列は存在しないということになります。

したがって、 $i = 0, 1, 2, ..., g-1$ について、S[ $\frac {iN} g$ ]　== T[ $\frac {iM} g$ ] を確かめるだけでよいことになります。

最大公約数についてはユークリッドの互除法が高速で便利です。コピペで使うライブラリを作ったので、リンクを貼っておきます。一応実装したことない人は一度やってみることをお勧めします。GitHubの扱いは不慣れですので何か間違ってたらごめんなさい。
Cpp_ComProLib/gcd at master · hewlae/Cpp_ComProLib · GitHub
最小公倍数は最大公約数ともとの2数N, Mから簡単に求められ、その値は $LCM(N, M) = \frac {NM}{GCD(N, M)}$ です。

▶ソースコードを開く

long gcd(long num1, long num2){
	if(num2 > num1){
		std::swap(num1, num2);
	}
	if(num2 == 0){
		return num1;
	}else{
		return gcd(num2, num1 % num2);
	}
}

long lcm(long num1, long num2){
	return num1 * num2 / gcd(num1, num2);
}

std::string s, t;
long n, m;

int main(){
	scanf("%ld%ld", &n, &m);
	std::cin >> s >> t;
	long g = gcd(n, m);
	for(int i = 0; i < g; i++){
		if(s[i*n/g] != t[i*m/g]){
			printf("-1\n");
			return 0;
		}
	}
	printf("%ld\n", lcm(n, m));
	return 0;
}