We present a practical algorithm for the cyclic longest common subsequence (CLCS) problem that runs in O(mn) time, where m and n are the lengths of the two input strings. While this is not necessarily an asymptotic improvement over the existing record, it is far simpler to understand and to implement.
The cyclic version of @math has seen more recent improvements. The first major improvement comes from @cite_1 , which uses a divide-and-conquer strategy to solve the problem in @math runtime. Since then, this approach has been applied to generalizations to the problem, and practical optimizations have been discovered; see @cite_2 for example. We describe the setup used in these papers in our preliminaries, though we build a different approach on top of this setup to arrive at our new algorithm. @cite_0 provides a solution that runs in @math time on arbitrary inputs, with asymptotically better performance on similar inputs; however, this solution requires considerable amounts of machinery both to understand and to implement.
@cite_0 @cite_1 @cite_2
2021202955 2122499640
We present an O(nm log m) algorithm to solve the string-to-string correction problem for cyclic strings. The matching of planar shapes can be cast as a problem of finding the shortest path through a graph spanned by the two shapes, where the nodes of the graph encode the local similarity of respective points on each contour. While this problem can be solved using dynamic time warping, the complete search over the initial correspondence leads to cubic runtime in the number of sample points. In this paper, we cast the shape matching problem as one of finding the shortest circular path on a torus. We propose an algorithm to determine this shortest cycle which has provably sub-cubic runtime. Numerical experiments demonstrate that the proposed algorithm provides faster shape matching than previous methods. As an application, we show that it allows to efficiently compute a clustering of a shape data base.