O (n ^ 2) (or O (n ^ 2lg (n))?) Algorithm for calculating the longest common subsequence (LCS) of two "ring" strings

Question

This is a problem that emerged at today's Pacific programmers contest in which no one solved it. This is issue B, and the full set of issues is here: http://www.acmicpc-pacnw.org/icpc-statements-2011.zip . There is a well-known O (n ^ 2) algorithm for two-line LCS using dynamic programming. But when these lines extend to the rings, I have no idea ...

PS note that this is a subsequence, not a substring, so the elements should not be adjacent to each other.

PS It may not be O (n ^ 2), but O (n ^ 2lgn) or something that can give a result after 5 seconds on a shared computer.

Answer 1

An Internet search appears to be considered in Section 4.3 of the article “Incremental String Comparison” by Landau, Myers, and Schmidt at cost O (ne) O (n ^ 2), where, I think, e is the editing distance. This article also mentions a previous article by Maes that gives the cost of O (mn log m) with more general editing costs - "On the loop line to fix the line." Expecting a participant to reproduce any of these articles seems pretty demanding to me, but as far as I can see, the question asks the longest common subsequence of looping lines.

Answer 2

, , .

Answer 3

"" . , LCS " ". (, Lij 0 ) . , , , - O (N) ( ), O (N ^ 3). , O (N ^ 2) ( , ) CLCS.

, O (N ^ 2), , - . CLCS "": CLCS p-times reapeated strings - p CLCS . , .

, : , Lc (N) CLCS N, | Lc (N) -CN | O (\ sqrt {N}), C - -. L (N) LCS , , , | L (N) -CN | O (sqrt (Nlog N)). Lc (N) L (N), .

: , CLCS , LCS. , , CLCS (X1X2, Y1Y2) CLCS (X1, Y1) + CLCS (X2, Y2) ( ). , Lc (N) (Lc (N1 + N2) Lc (N1) + Lc (N2)), , , . , Lc (N)/N N - ( , L (N)/N).

Answer 4

mcdowella , O (n ^ 2 lg n), , ( http://www.acmicpc-pacnw.org/ProblemSet/2011/solutions.zip). O (ne) . , , LCS. , , (, , ) (1, 1, 1). LCS, , (, , ) (1, 1, 2). ; , "ABC" "CXY" ( , ). LCS - "C", - .

110 , , , . Landau et al LCS, .

, : , CLCS O (n ^ 2) , : http://arxiv.org/abs/1208.0396 60 2 , . .