TEAMBOOK FFT в комплексных

#include <bits/stdc++.h>
using double_type   = double;
using long_type     = long long;
#define double  double_type
#define long    long_type
#define all(x) x.begin(), x.end()
using namespace std;

struct num {
    double a, b;
    num(double x, double y) :
        a(x),
        b(y) {}
    num() :
        a(0),
        b(0) {}
};
num operator+(const num &a, const num &b) {
    return {a.a + b.a, a.b + b.b};
}
num operator-(const num &a, const num &b) {
    return {a.a - b.a, a.b - b.b};
}
num operator*(const num &a, const num &b) {
    return {a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a};
}
void operator/=(num &a, double k) {
    a.a /= k;
    a.b /= k;
}
//~ num operator/(const num &a, const num &b) {
    //~ num c(b.a, -b.b);
    //~ c = a * c;
    //~ c /= b.a * b.a + b.b * b.b;
    //~ return c;
//~ }
istream &operator>>(istream &in, num &x) {
    return in >> x.a >> x.b;
}
ostream &operator<<(ostream &out, const num x) {
    return out << x.a << ' ' << x.b;
}

const int max_log   = 19;
const int max_len   = 1 << max_log;
const double pi = M_PIl;
int rev[max_len];

void fft_init(int k) {
    int n = 1 << k;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1;
        rev[i] |= (i & 1) << (k - 1);
    }
}

void fft_dir(num *a, int k) {
    int n = (1 << k);
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int h = 1; h < n; h *= 2) {
        double ang = pi / h;
        num mul(cos(ang), sin(ang));
        for (int st = 0; st < n; st += 2 * h) {
            num w(1, 0);
            for (int i = st; i < st + h; ++i) {
                num x = a[i], y = a[i + h];
                a[i]        = x + w * y;
                a[i + h]    = x - w * y;
                w = w * mul;
            }
        }
    }
}

void fft_inv(num *a, int k) {
    int n = (1 << k);
    fft_dir(a, k);
    for (int i = 0; i < n; ++i) {
        a[i] /= n;
    }
    reverse(a + 1, a + n);
}

int n, answer[max_len];
char first[max_len], second[max_len];
num a[max_len];

void solve(char ch) {
    fill(a, a + max_len, num());
    for (int i = 0; i < 2 * n; ++i) {
        a[i].a = (first[i % n] == ch);
    }
    for (int i = 0; i < n; ++i) {
        a[i].b = (second[n - 1 - i] == ch);
    }
    fft_dir(a, max_log);
    for (int i = 0; i < max_len; ++i) {
        a[i] = a[i] * a[i];
    }
    fft_inv(a, max_log);
    for (int i = 0; i < n; ++i) {
        answer[i] += round(a[n - 1 + i].b / 2);
    }
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
    assert(freopen("robots.in", "r", stdin));
    assert(freopen("robots.out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cerr << fixed << setprecision(3);
    cout << fixed << setprecision(3);

    cin >> n;
    cin >> first;
    cin >> second;
    fft_init(max_log);
    solve('A');
    solve('G');
    solve('C');
    solve('T');
    int *mx = max_element(answer, answer + n);
    cout << *mx << " " << mx - answer << "\n";
    return 0;
}