<p>As a followup to mcdowella's answer, I'd like to point out that the O(n^2 lg n) solution presented in Maes' paper is the intended solution to the contest problem (check <a href="http://www.acmicpc-pacnw.org/ProblemSet/2011/solutions.zip" rel="nofollow">http://www.acmicpc-pacnw.org/ProblemSet/2011/solutions.zip</a>).  The O(ne) solution in Landau et al's paper does NOT apply to this problem, as that paper is targeted at edit distance, not LCS.  In particular, the solution to cyclic edit distance only applies if the edit operations (add, delete, replace) all have unit (1, 1, 1) cost.  LCS, on the other hand, is equivalent to edit distances with (add, delete, replace) costs (1, 1, 2).  These are not equivalent to each other; for example, consider the input strings "ABC" and "CXY" (for the acyclic case; you can construct cyclic counterexamples similarly).  The LCS of the two strings is "C", but the minimum unit-cost edit is to replace each character in turn.  </p>

<p>At 110 lines but no complex data structures, Maes' solution falls towards the upper end of what is reasonable to implement in a contest setting.  Even if Landau et al's solution could be adapted to handle cyclic LCS, the complexity of the data structure makes it infeasible in a contest setting.</p>

<p>Last but not least, I'd like to point out that an O(n^2) solution DOES exist for CLCS, described here: <a href="http://arxiv.org/abs/1208.0396" rel="nofollow">http://arxiv.org/abs/1208.0396</a> At 60 lines, no complex data structures, and only 2 arrays, this solution is quite reasonable to implement in a contest setting.  Arriving at the solution might be a different matter, though.</p>
O(n^2) (or O(n^2lg(n)) ?)algorithm to calculate the longest common subsequence (LCS) of two 'ring' string
<p>This is a problem appeared in today's Pacific NW Region Programming Contest during which no one solved it. It is problem B and the complete problem set is here: <a href="http://www.acmicpc-pacnw.org/icpc-statements-2011.zip" rel="nofollow">http://www.acmicpc-pacnw.org/icpc-statements-2011.zip</a>. There is a well-known O(n^2) algorithm for LCS of two strings using Dynamic Programming. But when these strings are extended to rings I have no idea...</p>

<p>P.S. note that it is subsequence rather than substring, so the elements do not need to be adjacent to each other</p>

<p>P.S. It might not be O(n^2) but O(n^2lgn) or something that can give the result in 5 seconds on a common computer.</p>