O(n ^ 2)(或O(n ^ 2lg(n))？)算法计算两个'环'字符串的最长公共子序列(LCS)

Question

这是今天太平洋西北地区编程竞赛中出现的一个问题,在此期间没有人解决它.这是问题B,完整的问题集在这里:http://www.acmicpc-pacnw.org/icpc-statements-2011.zip.对于使用动态编程的两个字符串的LCS,存在众所周知的O(n ^ 2)算法.但是当这些字符串扩展到环时我不知道......

PS注意它是子序列而不是子串,因此元素不需要彼此相邻

PS它可能不是O(n ^ 2)而是O(n ^ 2lgn)或者可以在普通计算机上在5秒内给出结果的东西.

Answer 1

在网上搜索，这似乎在 Landau、Myers 和 Schmidt 的论文“增量字符串比较”的第 4.3 节中有所涉及，成本为 O(ne) < O(n^2)，其中我认为 e 是编辑距离。本文还引用了 Maes 之前的一篇论文，给出了成本 O(mn log m) 和更一般的编辑成本 - “On a circular string to string Correcting Problem”。期望参赛者重现这两篇论文中的任何一篇对我来说似乎要求很高 - 但据我所知，这个问题确实要求循环字符串上的最长公共子序列。