论文标题
有效测试西蒙的一致性
Efficiently Testing Simon's Congruence
论文作者
论文摘要
Simon的一致性$ \ sim_k $定义如下：如果最多$ k $具有相同长度的子序列，则两个单词是$ \ sim_k $ - 等效。我们提出了一种计算算法，给定两个单词$ s $和$ t $，这是$ s \ sim_k t $的最大$ k $。我们的算法在线性时间$ o（| s |+| t |）$中运行时，当输入单词在整数字母上$ \ {1，\ ldots，| s |+| t | \} $（或其他可以在线性时间分类的字母）。在一般字母的情况下，这种方法也会导致最佳算法。我们的结果基于一种新型的组合方法和一系列有效的数据结构。
Simon's congruence $\sim_k$ is defined as follows: two words are $\sim_k$-equivalent if they have the same set of subsequences of length at most $k$. We propose an algorithm which computes, given two words $s$ and $t$, the largest $k$ for which $s\sim_k t$. Our algorithm runs in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\{1,\ldots,|s|+|t|\}$ (or other alphabets which can be sorted in linear time). This approach leads to an optimal algorithm in the case of general alphabets as well. Our results are based on a novel combinatorial approach and a series of efficient data structures.
