在序列中查找元素包的算法

Question

假设我有一系列感兴趣的元素 A, B, C...穿插着无关符号x .我想从预定义距离内发生的一组预定义有趣组合中识别元素包。符号跨度之间可能存在重叠。例如在字符串 C x x A A x x C 中算法会检测到两倍的模式 A A C如果最大距离为 5。

例如说我的一组有趣的组合是:

A A C
A B C

我有一个序列:

B A x x C x x x A A x x x C

并且最大跨度为 5。

我的算法应该输出:

B A x x C -> A B C

并且将无法识别模式 A A C因为感兴趣的元素之间的跨度大于 5。

我的直觉说它是某种动态编程，但也许它只是我无法发现的众所周知的算法的一个实例。

关于什么是方法/解决方案的任何提示？

Answer 1

让我们指定一些名称来描述问题:
m = 数组序列的长度(在您的示例中为 14)n = 数组序列中唯一元素的总数(示例中为 3)k = 每个搜索区域的长度(示例中为 5)g = 您要查找的组数(示例中为 2)

一种选择是在大小为 k 的每个搜索区域中汇总您的数据。 .在你的例子中，像这样:

{B A x x C}
{A x x C x}
...

我们制作大小为 n 的向量对于每个部分，第一个元素代表第一种元素的外观，比如 A

B A x x C --> [1,1,1] (one appearance of each)
A x x C x --> [1,0,1]

等等。

我们可以为我们正在搜索的组做同样的事情:

{A A C} --> [2,0,1]  
{A B C} --> [1,1,1]

现在问题就很明显了。假设我们考虑搜索区域的摘要 [3,2,5] 和我们正在搜索的组的摘要 [0,1,2]，我们可以通过认识到我们有第二个元素有 2 个选项，第三个元素有 (5x4)/(1x2) 个选项，所以总共有 20 个选项。

因此，对于部分摘要 S, [s1, s2,..,sn] 和单个感兴趣的组 G, [g1, g2,...gn]，我们可以计算提取 G 的方式的总和来自 S(c++ 风格的代码，除了“!”表示阶乘):

int total_options = 1; // total ways to select G from S
for (int i = 0; i < n; ++i)
{
    if(g[i] == 0)
        continue; // this is an element that doesn't appear in G, so it shouldn't effect our count

    if(s[i] < g[i])
        return 0; // not enough elements in S for G

    for (int d = 1, f = s[i]; f > max(g[i], s[i] - g[i]); --f, ++d)
        total_options = total_options / d * f; // f, d are effectively factorials

    // the previous loop is a more efficient version of:
    // total_options *= (s[i]!) /(g[i]! * (s[i] - g[i])!);
}

return  total_options;

您将为每个部分以及您要搜索的每个组执行此操作。

时间复杂度:O( g*m*(k + n) )(我们必须在这里包含 k 因为最坏情况的阶乘计算)

空间复杂度:O( m + g*n )(我们可以边走边计算每个部分，因此无需同时存储多个部分)

然后我们可以通过意识到每个连续的“部分”仅通过考虑离开的“尾部”元素和进入的“头部”元素而有所不同来改进这一点，因此我们应该在迭代时计算这两个如何改变“选项计数”到下一节。我们将通过保持之前的“选项计数”计算以及 NF(失败次数)，即区域中对于搜索组来说太少的元素数量来实现这一点。诀窍是保持一个正的“选项计数”，只有当 NF 为 0 时，它才会被添加到总计中。这将为每个 G 提供恒定时间的结果。当您遍历大小为 m 的主数组时.

时间复杂度:O(g*m + g*n)
空间复杂度:O(g*n + m)

当主数组中的每个元素都是唯一的，并且这些元素中的每一个在某些搜索中至少出现一次时，该算法的性能最差(否则我们可以将任何未出现在任何搜索中的元素视为所有元素)相同，例如您的示例中的“x”)。因此，最坏情况的复杂性可以简化为:

时间复杂度:O(g*m)
空间复杂度:O(g*m)

我看不出如何获得更好的时间复杂度，但我很想知道是否有聪明的人能想到一种空间复杂度较低的方法。

如果仅考虑头部和尾部，当涉及到恒定时间迭代时，您不知道我在说什么，请告诉我，我将通过示例进行解释。