Максимизируйте [length(X)/2^(XOR(X, Y))], выбрав подстроки X и Y из строк A и B соответственно

Опубликовано: 22 Сентября, 2022

Даны две двоичные строки A и B размера N и M соответственно, задача состоит в том, чтобы максимизировать значение длины (X)/2 XOR(X, Y) , выбрав две подстроки X и Y одинаковой длины из заданной строки. А и Б соответственно.

Примеры:

Input: A = “0110”, B = “1101”
Output: 3
Explanation:
Choose the substring “110” and “110” from the string A and B respectively. The value of the expression of length(X) / 2XOR(X, Y) is 3 / 20 = 3, which is maximum among all possible combinations.

Input: A = “1111”, B = “0000”
Output: 0

Подход: Данную задачу можно решить, соблюдая выражение, что ее нужно максимизировать, поэтому знаменатель должен быть минимальным , а для ее минимизации значение побитового исключающего ИЛИ подстрок X и Y должно быть минимальным, т. е. равным нулю , и сделать значение побитового XOR равно нулю , две подстроки должны быть одинаковыми. Таким образом, задача сводится к поиску самой длинной общей подстроки строк A и B. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте двумерный массив, скажем, LCSuff[M + 1][N + 1] , чтобы хранить длины самых длинных общих суффиксов подстрок.
  • Инициализируйте переменную, скажем, результат как 0 , чтобы сохранить максимальное значение результата данного выражения.
  • Переберите диапазон [0, M], используя переменную i , и вложенный перебор диапазона [0, N], используя переменную j , и выполните следующие шаги:
    • Если i равно 0 или j равно 0 , то обновите значение LCSSuff[i][j] равным 0 .
    • В противном случае, если значение A[i – 1] равно A[j – 1] , тогда обновите значение LCSSuff[i][j] как LCSSuff[i – 1][j – 1] + 1 и обновите значение результат как максимум результата и LCSSuff[i][j] .
    • В противном случае обновите значение LCSSuff[i][j] до 0 .
  • После выполнения вышеуказанных шагов выведите значение результата в качестве результата.

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

Временная сложность: O(M*N)
Вспомогательное пространство: O(M*N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ