Задача №111890. Кластеризация тяжелых цепей
Группа биологов пытается найти лекарство от вирусного заболевания. Они перепробовали множество антител и оставили из них \(n\), которые лучше всего проявили себя в течение эксперимента.
Каждое антитело определяется тяжелой цепью – последовательностью аминокислот.
Набор антител считается похожим, если выполнено хотя бы одно из условий:
- \(k\)-префиксы (первые \(k\) аминокислот) тяжелых цепей равны
- \(k\)-суффиксы (последние \(k\) аминокислот) тяжелых цепей равны
Для упрощения дальнейших исследований биологам надо разбить антитела на минимально возможное число похожих наборов. Помогите им!
Первая строка содержит два целых числа \(n\) и \(k\) – число тяжелых цепей и длина последовательностей аминокислот, которая должна совпасть. (\(1 \leq n \leq 5000\), \(1 \leq k \leq 550\)).
Следующие \(n\) строк описывают последовательности аминокислот, которые образуют тяжелые цепи. Каждая аминокислота описывается заглавной латинской буквой. Каждая тяжелая цепь содержит не менее \(k\) и не более \(550\) аминокислот.
Первая строка выходного файла должна содержать одно число - минимальное число похожих наборов. Следующие строки должны содержать описания наборов по одному на строке.
Описание каждого набора должно начинаться с числа \(m_i\) - количества антител в наборе, за которым должно следовать \(m_i\) чисел – номера этих антител. Антитела пронумерованы в порядке описания во входном файле.
4 1 AA AB BB BA
2 2 1 2 2 3 4
3 2 ABA BAB XY
3 1 1 1 2 1 3