Two Abbreviations [ AtCoder Grand Contest 028 A ]

atcoder.jp

問題

省略

考察

※以下、0オリジン

問題文を

・Xの指定された部分を連結すると S,Tになる

ではなく、

・S,T を指定された通りに並べたとき、矛盾なく X を作ることができるか

と読み換えて考えます。

N=6, M=3 のとき、S,T は表のように並べることになります。

	0	1	2	3	4	5
S	S[0]	S[1]	S[2]	S[3]	S[4]	S[5]
T	T[0]		T[1]		T[2]

空白の部分はどんな文字でも構いませんが、S,T が重なっている部分は、同じ文字でなければいけません。

よってこの問題は、

・S,T を指定された通りに並べたとき、重なる部分が同じ文字であるか

を検証し、全ての部分について true であれば LCM(N, M) を出力、1個所でも false であれば -1 を出力、とすることで解くことができます。

そのためには、S,T のどの文字がどの位置で重なるかということを調べなくてはなりません。
上記の表でいうところの、S[0]=T[0], S[2]=T[1], S[4]=T[2] の添え字の部分をどうやって求めるか、ということです。

結論から言うと、K = GCD(N, M) としたとき、

・S[0*N/K] = T[0*M/K]
・S[1*N/K] = T[1*M/K]
・S[2*N/K] = T[2*M/K] ......

このような位置に S,T の重なりが存在します。
重なる回数は GCD(N, M) 回です。

よって、上記の位置で文字の一致を GCD(N, M) 回判定し、1つでも一致しなければ -1 、全て一致すれば LCM(N, M) を出力します。

コード

void solve (FastScanner in, PrintWriter out) {

	int n = in.nextInt(), m = in.nextInt();
	String s = in.next(), t = in.next();
	
	int gcd = (int)gcd(n, m);
	
	for (int i=0; i<gcd; i++) {
		if (s.charAt(i*n/gcd) != t.charAt(i*m/gcd)) {
			out.println(-1);
			return;
		}
	}
	
	out.println(lcm(n, m));
	
}

static long gcd (long a, long b) {return b>0?gcd(b,a%b):a;}
static long lcm (long a, long b) {return a/gcd(a,b)*b;}

正直に言うと全然わかっていません。
解説を書けば理解が深まるかと思っていましたがそんなことはありませんでした。