Это cложная версия задачи. В этой версии \(l\le r\).
Дана строка \(s\). Для фиксированного \(k\) рассмотрим деление \(s\) на ровно \(k\) непрерывных подстрок \(w_1,\dots,w_k\). Пусть \(f_k\) — максимально возможное \(LCP(w_1,\dots,w_k)\) среди всех делений.
\(LCP(w_1,\dots,w_m)\) — это длина самого длинного общего префикса строк \(w_1,\dots,w_m\).
Например, если \(s=abababcab\) и \(k=4\), то возможное деление \(\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}\). \(LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})\) равно \(2\), так как \(ab\) — самый длинный общий префикс этих четырех строк. Обратите внимание, что каждая подстрока состоит из непрерывного сегмента символов, и каждый символ принадлежит ровно одной подстроке.
Ваша задача — найти \(f_l,f_{l+1},\dots,f_r\).