假设我有一个由感兴趣的元素A、B、C...以及不关心的符号x交错组成的序列。我想要在预先定义的距离内识别出一些有趣的组合集，并且这些组合集来自于一个预先定义好的集合。这些符号之间的跨度可以重叠。例如，在字符串"C x x A A x x C"中，如果最大距离为5，则算法会检测到模式"A A C"两次。
例如，假设我的有趣组合集如下：
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
由于感兴趣元素之间的跨度大于5，因此它将无法识别模式A A C。
我的直觉告诉我这是一种动态规划算法，但也许它只是一个我无法发现的众所周知的算法实例。
有什么提示可以提供关于应该采取什么方法/解决方案吗？
{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]
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;
将所有有趣的组合构建成一棵树，使得有趣的组合导致叶子节点，而不有趣的则不是。首先排序，以便对应于早期符号的边更靠近根。
读取前五个元素，并增加相应的频率计数器，以记录每个元素出现的次数。
通过根据频率计数器遍历树来检查最多五个值的子集。如果到达叶子节点，则发出当前匹配。
为了滑动窗口，减少与当前最左侧有趣符号相关联的计数器，并增加向右滑动后吸入的有趣符号的计数器。
示例1：
AAC, ABC => (-) [B A x x C] x x x A A x x x C
| f[A] = 1, f[B] = 1, f[C] = 1
A A->B->C, emit ABC
|
(-) B [A x x C x] x x A A x x x C
/ \ f[B]--; A->x; continue
A B
| | B A x x [C x x x A] A x x x C
(-) (-) f[A]--; f[A]++; A->x; continue
| |
C C B A x x C x x x [A A x x x] C
| | f[C]--; f[A]++; A->A->x; continue
(+) (+)
B A x x C x x x A [A x x x C]
f[A]--; f[C]++; A->x; done
AAC => (-) [C x x A A] x x C
| f[A]=2, f[B]=0, f[C]=1
A A->A->C, emit AAC; continue
|
(-) C x x [A A x x C]
| f[C]--; f[C]++; A->A->C; emit AAC; done
A
|
(-)
|
C
|
(+)
这个解决方案应该可以适用于不同的窗口大小，甚至可以通过将内部节点标记为匹配（而不仅仅是叶子节点）来允许有趣的不同大小的组合。这将在输入流中的元素数量方面具有线性时间和空间复杂度，尽管它将需要一些额外的内存，以便记录有趣的组合和窗口大小的数量。具体的时间/空间分析留作练习。
5:AB [AAxBB] 应该计为 4。事实上，我认为 4:AB [AAxBB] 也应该计为 4。我不认为你的算法能够做到这一点... - RBarryYoung(字符搜索计数+1) - (字符发现计数)的乘积来进行调整。 - RBarryYoung