Алгоритм O (n ^ 2) (или O (n ^ 2lg (n))?) Для вычисления Самая длинная общая подпоследовательность (LCS) из двух «кольцевых» строк

Это проблема, появившаяся на сегодняшнем соревновании по программированию в Тихоокеанском Северо-западном регионе, в ходе которого ее никто не решил. . Это проблема B, и полный набор задач находится здесь: http://www.acmicpc-pacnw.org/icpc-statements-2011.zip . Существует хорошо известный алгоритм O (n ^ 2) для двухстрочного LCS с использованием динамического программирования. Но когда эти строки расширяются до колец, я понятия не имею ...

P.S. обратите внимание, что это подпоследовательность, а не подстрока, поэтому элементы не обязательно должны быть смежными друг с другом

P.S. Это может быть не O (n ^ 2), а O (n ^ 2lgn) или что-то, что может дать результат за 5 секунд на обычном компьютере.