У меня есть две строки s1 и s2. Мне нужно найти подстроку в s1 с длиной s2, которая имеет наибольшее количество символов, соответствующих s2. Обе строки имеют длину меньше или равную N. Как мне это сделать за время O (N log N) в наихудшем случае?
Изменить: более формальное определение проблемы. Для двух заданных строк s1, s2 найдите такое K, что len(s1)>len(s2)+K-1 и f(K) максимально, где f(n) определяется формулой
f(n) = |{j : s1[K+j]==s2[j]}|