Максимизируйте данную функцию, выбрав подстроки равной длины из заданных двоичных строк.

Даны две бинарные строки s1 и s2 . Задача состоит в том, чтобы выбрать подстроку из s1 и s2 , скажем, sub1 и sub2 одинаковой длины, чтобы она максимизировала функцию:

fun(s1, s2) = len(sub1) / (2^{xor(sub1, sub2)})

Примеры:

Input: s1= “1101”, s2= “1110”
Output: 3
Explanation: Below are the substrings chosen from s1 and s2
Substring chosen from s1 -> “110”
Substring chosen from s2 -> “110”
Therefore, fun(s1, s2) = 3/ (2^{xor(110, 110)}) = 3, which is maximum possible. 

Input: s1= “1111”, s2= “1000”
Output: 1

Подход: чтобы максимизировать данную функцию, необходимо выбирать большие подстроки с минимальным XOR. Чтобы свести к минимуму знаменатель, выбирайте подстроки таким образом, чтобы исключающее ИЛИ sub1 и sub2 всегда было равно 0 , так что член знаменателя всегда будет равен 1 (2 ⁰ ). Итак, для этого найдите самую длинную общую подстроку из двух строк s1 и s2 и выведите ее длину, которая будет требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M), где N — размер s1, а M — размер s2.

Вспомогательное пространство: O(N*M), где N — размер s1, а M — размер s2.