论文标题
重新审视最长的正方形子序列问题
Longest Square Subsequence Problem Revisited
论文作者
论文摘要
最长的正方形子序列（LSS）问题包括计算给定的字符串$ s $的最长子序列，即正方形，即出现在$ s $中的表单$ xx $的最长子序列。众所周知，可以使用$ o（n^2）$ time [Kosowski 2004]或使用$ O（n^2（\ log log \ log \ log \ log \ log \ log \ log n）^2 / \ log^2 n）$ [tiskin 2013]来计算$ n $的字符串$ s $长度$ s $。我们介绍了LSS的第一个算法，其运行时间取决于其他参数，即，我们表明可以以$ O（r \ min \ {n，m \} \ log \} \ log \ frac {n} {r} {r} + n + n + m \ log n + m \ log n）$ ls $ o（m）$（$ o（m）$（$ o（m）$（$ o（m min）， $ m $是$ S $上的匹配点数。
The longest square subsequence (LSS) problem consists of computing a longest subsequence of a given string $S$ that is a square, i.e., a longest subsequence of form $XX$ appearing in $S$. It is known that an LSS of a string $S$ of length $n$ can be computed using $O(n^2)$ time [Kosowski 2004], or with (model-dependent) polylogarithmic speed-ups using $O(n^2 (\log \log n)^2 / \log^2 n)$ time [Tiskin 2013]. We present the first algorithm for LSS whose running time depends on other parameters, i.e., we show that an LSS of $S$ can be computed in $O(r \min\{n, M\}\log \frac{n}{r} + n + M \log n)$ time with $O(M)$ space, where $r$ is the length of an LSS of $S$ and $M$ is the number of matching points on $S$.
