考虑S第一个字符，会和T中哪些位置上的数配对。
其实就是 \(k|S|\mod |T|\)。
然后可以打表找规律：
int main() {
int a, b;
cin >> a >> b;
int x = 0;
vector<int> all;
while (x < a * b) {
all.push_back(x % b);
x += a;
}
sort(all.begin(), all.end());
for (int i : all) cout << i << ' ';
return 0;
}
发现序列和\(gcd(|S|,|T|)\)有关，具体来说是\(d = gcd(|S|,|T|)\)，那么先有 \(d\) 个0，\(d\) 个 \(d\)，\(d\) 个 \(2d\) ，……，一直到\(d\)个\(kd,(k+1)\ge|T|\)。
那么对于这个位置的贡献，只需要枚举\(T\)中\(kd\)位置的值，判断是否相等，如果是就加上\(d\)的贡献。
比如长度分别是12和20。
x=0：0 0 0 0 4 4 4 4 8 8 8 8 12 12 12 12 16 16 16 16 。
x=1：1 1 1 1 5 5 5 5 9 9 9 9 13 13 13 13 17 17 17 17 。
x=2：2 2 2 2 6 6 6 6 10 10 10 10 14 14 14 14 18 18 18 18 。
x=3：3 3 3 3 7 7 7 7 11 11 11 11 15 15 15 15 19 19 19 19 。
x=4：0 0 0 0 4 4 4 4 8 8 8 8 12 12 12 12 16 16 16 16 。
……
不难发现，从x=k的地方出发，相当于以\(d\)为循环节，首项是\(k\mod d\)，公差是\(d\)的数列。
写出如下无关\(n, m\)的代码：
int main() {
cin >> a >> b >> s >> t;
int d = gcd(s.size(), t.size());
int res = 0;
for (int x = 0; x < s.size(); x ++ ) {
int cnt = 0;
for (int y = x % d; y < t.size(); y += d)
if (s[x] == t[y]) cnt ++ ;
res = res + cnt * d;
}
cout << res << endl;
return 0;
}
复杂度\(O(\frac{|S||T|}{d})\)。