In a sequence, approximate patterns are exponential in number. In this paper, we present a new notion of basis for the patterns with don't cares occurring in a given text (sequence). The primitive patterns are of interest since their number is lower than previous known definitions (and in a case, sub-linear in the size of the text), and these patterns can be used to extract all the patterns of a text. We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q ― 1 times, in time O(|Σ|N n~2 log~2 n log log n). In the particular case where q = 2, the complexity in time is only O(|Σ|n~2 log~2 n log log n). We also give an algorithm that decides if a given pattern is primitive in a given text.
展开▼
机译：在一个序列中，近似模式的数量是指数的。在本文中，我们为给定文本（顺序）中出现无关紧要的模式提供了新的基础概念。由于原始模式的数量少于先前的已知定义（并且在某种情况下，文本大小为次线性），因此原始模式受到关注，并且这些模式可用于提取文本的所有模式。我们给出了一种增量算法，该算法计算在长度为n的文本中至少出现q次的原始模式，给定N个出现至少q ― 1次的原始模式，时间为O（|Σ| N n〜2 log〜2 n日志日志n）。在q = 2的特定情况下，时间复杂度仅为O（|Σ| n〜2 log〜2 n log log n）。我们还给出了一种算法，该算法可以确定给定模式在给定文本中是否为原始类型。
展开▼
