数論っぽい。

問題

長さの等しい文字列$s,t$が与えられる。 それぞれ文字列$x,y$の$n,m$回の繰り返しとして表現される。 そのhamming距離を求めよ。

解法

gcdやlcmでまとめる。文字種$L = 26$として$O((|x| + |y|)L)$。

余分な繰り返しは、単純にその回数倍すればよい。以下は長さが一致するのに必要な最小回数の繰り返しだけを考える。

つまり$x,y$の文字列長が互いに素だとする。 このとき$\{ (s_i, t_i) \mid i \} = \{ (x_i, y_j) \mid i, j \}$となる。 したがって、それぞれの文字種に関してその出現回数を数え、適当に掛けて足せばよい。

例えばabcdとxyzに関して、

abcdabcdabcd
xyzxyzxyzxyz

となるが、a,x a,y a,z b,x b,y` $\dots$と全ての組がちょうと1度ずつ出現しているのが分かる。

$x,y$の文字列長が互いに素ではないとする。 このとき$\{ (s_i, t_i) \mid i \} = \{ (x_i, y_j) \mid i == j \pmod {\gcd(|x|, |y|)} \}$となる。

例えばabcd uvwxyzとすると、

abcdabcdabcd
uvwxyzuvwxyz

となるが、$x,y$をac uwyとしたとき、$x,y$をbd vxzとしたときに出現するような対のみがちょうど出現している。 あとは互いに素の場合と同様である。

実装

このコードでいう所のam, bmは片方だけでもよいと思う。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) { if (b < a) swap(a,b); while (a) { ll c = a; a = b % c; b = c; } return b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int main() {
    ll an, bn; cin >> an >> bn;
    string a, b; cin >> a >> b;
    int al = a.length();
    int bl = b.length();
    int d = gcd(al, bl);
    vector<vector<int> > am(d, vector<int>(26));
    vector<vector<int> > bm(d, vector<int>(26));
    repeat (i,al) am[i % d][a[i] - 'a'] += 1;
    repeat (i,bl) bm[i % d][b[i] - 'a'] += 1;
    ll acc = 0;
    int bld = bl / d;
    repeat (i,d) {
        repeat (j,26) {
            acc += am[i][j] *(ll) (bld - bm[i][j]);
        }
    }
    acc *= gcd(an, bn);
    cout << acc << endl;
    return 0;
}