#include <stdio.h>
#include <cassert>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <string>
#include <iostream>
typedef unsigned long long ull;
// Генерация случайного основания в (before, after) открытом интервале:
int gen_base(const int before, const int after) {
auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt_rand(seed ^ ull(new ull));
int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
return base % 2 == 0 ? base-1 : base;
}
struct PolyHash {
// -------- Статические переменные --------
static const int MOD = 2147483647;
static std::vector<int> pow1; // степени основания по модулю MOD
static std::vector<ull> pow2; // степени основания по модулю 2^64
static int base; // основание (точка) хэширования
// --------- Статические функции --------
static inline int diff(int a, int b) {
// Разность между `a` и `b` по модулю MOD (0 <= a < MOD, 0 <= b < MOD)
return (a -= b) < 0 ? a + MOD : a;
}
static inline int mod(ull x) {
// Смещенный остаток от деления x на MOD (только для MOD = 2^31-1):
x += MOD;
x = (x >> 31) + (x & MOD);
return int((x >> 31) + (x & MOD));
}
// -------------- Переменные класса -------------
std::vector<int> pref1; // Полиномиальный хэш на префиксе по модулю MOD
std::vector<ull> pref2; // Полиномиальный хэш на префиксе по модулю 2^64
// Конструктор от строчки:
PolyHash(const std::string& s)
: pref1(s.size()+1u, 0)
, pref2(s.size()+1u, 0)
{
// Предподсчет степеней основания:
while (pow1.size() <= s.size()) {
pow1.push_back(mod((ull)pow1.back() * base));
pow2.push_back(pow2.back() * base);
}
// Заполнение массивов с хэшем на префиксе:
for (int i = 0; i < (int)s.size(); ++i) {
pref1[i+1] = mod(pref1[i] + (ull)s[i] * pow1[i]);
pref2[i+1] = pref2[i] + s[i] * pow2[i];
}
}
// Полиномиальный хэш от подпоследовательности [pos, pos+len)
// Если mxPow != 0, значение автоматически домножается на основание в
// нужной степени при доведении до степени base ^ mxPow:
inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
int hash1 = diff(pref1[pos+len], pref1[pos]);
ull hash2 = pref2[pos+len] - pref2[pos];
if (mxPow != 0) {
hash1 = mod((ull)hash1 * pow1[mxPow-(pos+len-1)]);
hash2 *= pow2[mxPow-(pos+len-1)];
}
return std::make_pair(hash1, hash2);
}
// Полиномиальный хэш на префиксе [0, len) после обмена символов ci и cj на
// позициях i и j:
inline std::pair<int, ull> prefix_after_swap(const int len, const int i, const int j, const char ci, const char cj) const {
// Префикс до i:
int hash1 = pref1[std::min(len, i)];
ull hash2 = pref2[std::min(len, i)];
if (len <= i) return std::make_pair(hash1, hash2);
// Добавления символа cj на позицию i:
hash1 = mod(hash1 + (ull)cj * pow1[i]);
hash2 += cj * pow2[i];
// Префикс до j:
hash1 = mod(hash1 + (ull)diff(pref1[std::min(len, j)], pref1[i+1]));
hash2 += pref2[std::min(len,j)] - pref2[i+1];
if (len <= j) return std::make_pair(hash1, hash2);
// Добавление символа на позицию j:
hash1 = mod(hash1 + (ull)ci * pow1[j]);
hash2 += ci * pow2[j];
// Префикс до len:
hash1 = mod(hash1 + (ull)diff(pref1[len], pref1[j+1]));
hash2 += pref2[len] - pref2[j+1];
return std::make_pair(hash1, hash2);
}
};
// Инициализация статических переменных класса:
int PolyHash::base((int)1e9+7);
std::vector<int> PolyHash::pow1{1};
std::vector<ull> PolyHash::pow2{1};
int solve(const int n, const std::string& s, const std::string& t) {
// Генерация случайного основания:
PolyHash::base = gen_base(256, PolyHash::MOD);
// Построение полиномиального хэша на строках S и T:
PolyHash hash_s(s), hash_t(t);
// Поиск первого несовпадающего символа:
int pos1 = 0;
while (pos1 < n && s[pos1] == t[pos1]) ++pos1;
// Пытаемся поменять pos1 с каждым символом после pos2 по очереди:
int answ = pos1;
for (int pos2 = pos1+1; pos2 < n; ++pos2) {
// Применяем бинарный поиск для нахождения наибольшего общего префикса после обмена:
int low = 0, high = n+1;
while (high-low > 1) {
const int mid = (low + high) / 2;
const auto hs = hash_s.prefix_after_swap(mid, pos1, pos2, s[pos1], s[pos2]);
if (hs == hash_t(0, mid)) {
low = mid;
} else {
high = mid;
}
}
// Обновляем ответ:
answ = std::max(answ, low);
}
return answ;
}
int main() {
// Чтение:
int n;
scanf("%d", &n);
char buf[1+200000];
scanf("%200000s", buf);
std::string s(buf);
scanf("%200000s", buf);
std::string t(buf);
// Решение задачи и вывод ответа:
printf("%d", solve(n,s,t));
return 0;
}