title: O(n^2) (or O(n^2lg(n)) ?)algorithm to calculate the longest common subsequence (LCS) of two 'ring' string
body: <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>