Consideremos el primer carácter de la cadena S y con qué posiciones de T se empareja. Esto se reduce a evaluar k|S| mod |T|.

Se puede explorar tabulando para descubrir patrones:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int lenA, lenB;
    cin >> lenA >> lenB;
    int current = 0;
    vector<int> residues;
    while (current < lenA * lenB) {
        residues.push_back(current % lenB);
        current += lenA;
    }
    sort(residues.begin(), residues.end());
    for (int val : residues) cout << val << " ";
    return 0;
}

Se observa que la secuencia generada está relacionada con d = gcd(|S|, |T|). Específicamente, aparecen d ceeros, luego d valores iguales a d, después d valores iguales a 2d, y así sucesivamente hasta llegar al múltiplo de d más cercano sin exceder |T|.

Para calcular la contribución de una posición, basta iterar sobre los índices de T que son múltiplos de d, verificar si coinciden con el carácter correspondiente de S, y de ser así añadir d al total.

Por ejemplo, con longitudes 12 y 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
...

Se deduce que partiendo de x=k, la secuencia tiene período d, primer término k mod d y diferencia común d.

Implementación inicial con complejidad O(|S||T|/d):

#include <iostream>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int lenS, lenT;
    string strS, strT;
    cin >> lenS >> lenT >> strS >> strT;
    int step = gcd(strS.size(), strT.size());
    long long total = 0;
    for (size_t posS = 0; posS < strS.size(); ++posS) {
        int matches = 0;
        for (size_t posT = posS % step; posT < strT.size(); posT += step) {
            if (strS[posS] == strT[posT]) ++matches;
        }
        total += matches * step;
    }
    cout << total << endl;
    return 0;
}

Dado que grupos de índices como 0,4,8,..., 1,5,9,..., 2,6,10,... comparten los mismos caracteres en T, se produce redundencia. Se propone agrupar el cálculo y solo contar frecuencias de cada letra:

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cstring>

using namespace std;

int main() {
    int lenS, lenT;
    string strS, strT;
    cin >> lenS >> lenT >> strS >> strT;
    int step = gcd(strS.size(), strT.size());
    long long result = 0;
    vector<int> freq(26, 0);
    for (int offset = 0; offset < step; ++offset) {
        memset(freq.data(), 0, freq.size() * sizeof(int));
        for (size_t i = offset; i < strT.size(); i += step) {
            ++freq[strT[i] - 'a'];
        }
        for (size_t i = offset; i < strS.size(); i += step) {
            result += freq[strS[i] - 'a'] * step;
        }
    }
    cout << result << endl;
    return 0;
}

Cada carácter de T solo se visita una vez cuando offset = i mod step, y análogamente para S. La complejidad resultante es O(|S|+|T|).

La corrección del algoritmo se verificó mediante pruebas aleatorias. Un generador de datos de ejemplo:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <numeric>

using namespace std;

int main() {
    srand(time(0));
    int n = rand() % 1000000 + 1;
    int m = rand() % 1000000 + 1;
    long long lcm_val = (long long)n * m / gcd(n, m);
    if (lcm_val / n > 1e9 || lcm_val / m > 1e9)
        cout << n << " " << m << "\n";
    else
        cout << lcm_val / n << " " << lcm_val / m << "\n";
    for (int i = 0; i < n; ++i) cout << (char)('a' + rand() % 26);
    cout << "\n";
    for (int i = 0; i < m; ++i) cout << (char)('a' + rand() % 26);
    return 0;
}