论文标题
基因一致的等效关系下的计算覆盖率
Computing Covers under Substring Consistent Equivalence Relations
论文作者
论文摘要
盖子是字符串中的一种准二元性。如果在$ t $中发生$ c $的任何位置，则字符串$ c $是另一个字符串$ t $的封面。 $ t $的最短和最长的封面阵列的长度分别为$ t $的每个前缀的最短和最长的封面。文献提出了线性时间算法计算最长和最短的覆盖阵列，以边框阵列作为输入。字符串上的等价关系$ \大约$ $ \ $称为子字符串一致的等价关系（SCER），如果f $ x \ y $表示（1）$ | x | = | y | $和（2）$ x [i：j] \大约y [i：j] $，for $ 1 \ le i \ le i \ le j \ le | x | $。在本文中，我们概括了SCERS的封面概念，并证明了现有的算法来计算身份关系下的最短封面阵列和字符串$ t $的最长封面阵列将适用于采用相应概括的边框阵列的任何SCER。
Covers are a kind of quasiperiodicity in strings. A string $C$ is a cover of another string $T$ if any position of $T$ is inside some occurrence of $C$ in $T$. The shortest and longest cover arrays of $T$ have the lengths of the shortest and longest covers of each prefix of $T$, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation $\approx$ over strings is called a substring consistent equivalence relation (SCER) iff $X \approx Y$ implies (1) $|X| = |Y|$ and (2) $X[i:j] \approx Y[i:j]$ for all $1 \le i \le j \le |X|$. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string $T$ under the identity relation will work for any SCERs taking the accordingly generalized border arrays.
