Задали задачу, про _неточный_ поиск подстроки s2 в строке s1
Я прочитал в вики про https://en.wikipedia.org/wiki/Approximate_string_matching
И по ссылкам оттуда, например Bitap

Но это не подошло. У этих алгоритмов сложность порядка |s1| * |s2|, а требуется O(n log(n)). Что такое правда неясно, но наверное имели ввиду длину |s1|.
Есть всякие алгоритмы быстрого поиска подстрока в строке за O(N) и O(N-1), но в требуется полное совпадение, а не нахождение максимального.
Каким алгоритмом можно решить такую задачу? Есть ли ключевые слова для гугла? ( fuzzy search, как видно я попробовал, но неудачно, находятся алгоритмы сложнее чем просят ).

Писать за меня код не надо, я просто не знаю в какую сторону думать

--------------------------------------------
Условие задачи:

Известно, что каждая клетка организма человека содержит ДНК, которая представляет из себя цепочку нуклеотидов, кодируемых символами A, G, T, C, и, кроме того, что эти цепочки у близких родственников должны быть похожими.
Для определения того, принадлежат ли два заданных ДНК s1 и s2 близким родственникам, вам нужно решить следующую задачу. Необходимо найти такую позицию i (позиции нумеруются с единицы) в строке s1, что, если приложить s2 к s1, начиная с позиции i, то, во-первых, каждому символу s2 будет соответствовать какой-то символ s1 (то есть s2 не выйдет за пределы s1), а во-вторых, количество соответствующих друг другу совпадающих символов в s1 и s2 будет максимально возможным. Другими словами, мощность множества {j: s2[j] = s1[j+i]} — максимально возможная из всех таких i. Если таких позиций i несколько, найдите первую из них.
Решение должно работать за O(n log n) в худшем случае

ввода: На входе две непустые строки s1 и s2 длины не более 200 000, причем s2 не длиннее, чем s1.
вывод: Выведите номер искомой позиции.