Это простая версия задачи. В этой версии \(l=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\). В этой версии \(l=r\).
Примечание
В первом примере \(n=k\), поэтому единственное деление \(aba\) — \(\color{red}a\color{blue}b\color{orange}a\). Ответ — ноль, потому что у этих строк нет общего префикса.
Во втором примере единственное деление — \(\color{red}a\color{blue}a\color{orange}a\). Их самый длинный общий префикс равен одному.