Привет всем. Такая проблема: разобрался с базовыми алгоритмами на строках (префикс-функции и Z-функции), почитал про их применение (поиск подстроки в строке, сжатие строки, поиск количества различных подстрок), понял, вроде все нормально.
Проблема начинается на практике: сколько встречал задач уровня D(Div2)/B(Div1) на строки, сразу определял, что задача будет на эти структуры, но дальше дело не заходило — решать задачи абсолютно не получается. Каноничный пример задачи — D с последнего контеста в div2 (http://mirror.codeforces.com/contest/535/problem/D).
Может кто подскажет, как проще найти тот связующий мостик между теорией и практикой? Может есть статьи на тему более нетривиального применения, чем базовые возможности этих структур? Или может есть примеры задач, на которых все учились, и которые как раз-таки формируют полное понимание?
На мой взгляд, эта задача требует только теоретического знания о Z-функции, а после ее реализации сводится к задаче типа "AdHoc".
Кроме как "решать больше задач" вряд ли что-нибудь можно посоветовать.
Ну ты же знаешь, что умеет z-функция? Она показывает для каждого суффикса строки длину LCP этого суффикса и всей строки целиком. Потом просто думаешь, как можно использовать эту инфу, и получаешь Accepted.
Спасибо за ответы ;)