Войти Регистрация
Алгоритмы

119. Самый длинный общий фрагмент двух сообщений

Сложная

Даны строки a и b — тексты двух сообщений. Верните длину самой длинной строки, которая встречается непрерывным куском и в a, и в b.

Если общих символов нет или одна из строк пустая, ответ 0.

В работе: Антиспам VK Мессенджера: длинный общий кусок у сотни сообщений с разных аккаунтов — признак рассылки по шаблону.

Пример 1

Ввод
a = "скидкаджинсы"
b = "новыеджинсыуже"
Вывод
6

Общий кусок «джинсы» — 6 символов.

Пример 2

Ввод
a = "abc"
b = "xyz"
Вывод
0

Общих символов нет.

Ограничения

  • 0 ≤ длина a, длина b ≤ 5·10⁴
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def longest_common_piece(a, b):
СтрокиПолиномиальный хешБинарный поискцельO(n log n)

Источник: наша задача на данных VK. Условие пересказано своими словами.