Блог пользователя RiarioRovere

Автор RiarioRovere, история, 9 лет назад, По-русски

Доброго времени суток. Помогите, пожалуйста, решить задачу из ИОИП 2014 года. Разбора не нашел. http://codeforces.me/gym/100397

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

Ну самое простое решение: посчитать хеши строк, чтобы быстро все сравнивать. Теперь проверим подойдет ли нам позиция p. Для этого бинарным поиском найдем максимальную длину префикса строки t, совпадающей с префиксом строки s[p..]. Пусть эта длина равна l. Нам осталось убедится, что символ s[p+l] != t[l] (индексация с нуля), s[p+l+k] != t[l+k], и с помощью хешей проверить совпадение 2 подстрок (суффикса строки t и серединки строки t). Получим решение за O(|s| * log(|s|) + |t|). С помощью Z-функции можно получить решение за время O(|s| + |t|).