Описание задачи
Работа со связным списком строк (стихов). Нужно найти "похожие" строки — те, которые являются циклическими сдвигами друг друга.
Критерий похожести
Строка A похожа на B, если A является циклическим сдвигом B.
"Progtest" ≡ "rogtestP" ≡ "ogtestPr" ≡ "gtestPro" ≡ ...
Трюк: A является циклическим сдвигом B ⟺ A содержится в B+B.
Задача
- Найти самую большую группу похожих строк
- Вернуть новый связный список с копиями этих строк
- Сохранить порядок из оригинального списка
Функция
List* vogonPoetry(List* src)
→ новый список с самой большой группой
Пример
Входной список
"ABC" → "CAB" → "XYZ" → "BCA" → "ZYX" → "YZX"
Группы
Группа 1: "ABC", "CAB", "BCA" (3 элемента)
Группа 2: "XYZ", "YZX", "ZXY"? Нет, "ZYX" ≠ "XYZ" shifted
Только "XYZ", "YZX" похожи? Проверяем:
"XYZ" → "YZX" → "ZXY" → "XYZ"
"ZYX" → "YXZ" → "XZY" → "ZYX"
Разные группы!
Результат
"ABC" → "CAB" → "BCA"
Ключевые моменты
- Канонизация: для группы выбрать минимальный сдвиг как ключ
- Или использовать двойную строку: A ⊂ B+B
- Собрать группы → выбрать максимальную → скопировать
- Сохранить относительный порядок