Заочные олимпиады: 2 тур

Алиса и Аня работают копирайтерами. Недавно им пришёл заказ: нужно написать \(k\) текстов (строк) на схожую тематику. Девочки сразу приступили к работе и быстро получили \(k\) строк \(S_1, \dotsc, S_k\), каждая из которых имеет длину не более \(m\) и состоит из строчных латинских букв, при чем длина \(S_1\) оказалсь в точности равна \(m\).

Девочки уже давно работают вместе, и у них есть простой способ проверить оригинальность своей работы. Оригинальность оценивается с помощью подстрок полученных текстов. Алиса и Аня считают некоторую строку неоригинальной, если и она, и строка, получающаяся из данной разворотом, встречаются в некоторых из их текстов в качестве подстрок на одних и тех же позициях.

Чтобы ускорить проверку, они разбивают строки на блоки. Разбиение на \(t\) блоков задается последовательностью \(a_0, a_1, \dotsc, a_t\), где \(a_0 = 0\), \(a_t = m\) и \(a_{i-1} < a_{i}\) для любого \(1\le i\le t\). Тогда \(i\)-м блоком называется отрезок целых чисел \([a_{i-1}+1; a_i]\). Блок \([a_{i-1}+1; a_i]\) называется интересным, если существует неоригинальная строка, встречающаяся в текстах ровно на позициях, задаваемых данным блоком. Иными словами, блок — интересный, если для каких-то строк \(S_l\) и \(S_r\) (возможно, \(l = r\)) верно, что \(|S_l|,|S_r| \ge a_i\), и строка \(S_{l,\,a_{i-1}+1}S_{l,\,a_{i-1}+2}\dotsc S_{l,\,a_i}\) совпадает со строкой \(S_{r,\,a_i}S_{r,\,a_i-1}\dotsc S_{r,\,a_{i-1}+1}\), где \(S_{t,j}\) — \(j\)-й слева символ строки \(S_t\).

Например, для текстов [ abba , ba ] последовательности \((0,1,4)\) и \((0,1,2,3,4)\) задают корректные разбиения, а последовательности \((1,2,3)\) и \((0,1,1,4)\) — нет. При этом для разбиения \((0,2,4)\) первый блок \([1;2]\) является интересным, поскольку \(S_{1,1}S_{1,2}=S_{2,2}S_{2,1}=\) ab , а второй блок \([3;4]\) — нет, поскольку для единственной возможной пары номеров \(l = r = 1\) строки \(S_{1,3}S_{1,4}=\) ba и \(S_{1,4}S_{1,3}=\) ab не совпадают.

Разбиение называется интересным, если каждый блок в этом разбиении интересный. Алиса и Аня хотят найти интересное разбиение текстов на минимальное число блоков, чтобы измерить оригинальность работы. Девочки постарались, чтобы условие этой задачи было современным и прошло тест Бекдел, поэтому теперь помогите им и напишите для них программу, измеряющую оригинальность!

Заметим, что искомая величина корректно определена, так как, разбив строки на \(m\) блоков длины \(1\), мы получим интересное разбиение (в каждом блоке будет достаточно взять \(l = r = 1\)).