以暴力方式用指数运行时间解决此匹配

Question

我有一个关于匹配的问题。表述如下。

我有一个由两个字符 {l,h} 组成的序列。

比如我有一个长度为6的序列（我称之为原始序列），它是[h,l,h,l,h,l] . 这个序列可以通过上面的映射规则转化为详细序列。一个详细的序列可以是[6,1,5,2,4,3]。而对于长度为6的序列，有6^3个详细序列。

我通过计算成对差异从详细序列中获得了一个差异序列。比如我的详细序列是[6,1,5,2,4,3]，那么对应的差分序列就是[6-1,1-5,5-2,2-4,4-3] = [ 5,-4,3,-2,1]。因此，差分序列的一个条目的最大值是6减1得到的5，最小值是1减6得到的-5。

现在，我有一个包含 m 个长度为 5 的差异序列的数据库。我的查询序列是一个长度为6的原始序列。我想找到：

在m个不同的序列中，对应的原始序列有哪些可以作为我的查询序列。如果它们不存在，程序将 return 设置为空。如果它们存在，程序将 return 由它们组成的集合。

例如，对于一个差分序列[5,-4,3,-2,1]，其对应的原始序列可以是[h,l,h,l,h,l]。因此，如果我的查询序列是 [h,l,h,l,h,l]，[5,-4,3,-2,1] 将在 returned 集合中，如果 [5,- 4,3,-2,1] 在数据库中。

对于我的实际问题，查询序列的长度为 n。数据库由m个长度为n-1.

的差异序列组成

暴力破解方法可以如下：对于输入的原始序列，枚举其3^n个详细序列，得到3^n个差分序列。对于每个差异序列，检查它是否存在于数据库中。
蛮力将花费 O(3^n)。我知道这个指数运行时间不好

我想要一个更快的算法。一个近似算法对我来说也不错。

非常感谢。

Answer 1

每个差异序列最多可以从四个 h-l 序列创建。

因此，预处理您的数据库以构建从 h-l 序列到您感兴趣的差异序列的索引。

例如：

[1, -1, 0, 2, -1]

这必须来自以下序列之一：

[3 2 3 3 1 2] -> l l l l l l 
[4 3 4 4 2 3] -> h l h h l l
[5 4 5 5 3 4] -> h h h h l h
[6 5 6 6 4 5] -> h h h h h h

您可以通过从 1 到 6 的特定序列开始并应用差异来生成它们。有时序列会下溢或溢出 1..6 的合法范围，然后您可以放弃这种可能性。

建立这个索引是 O(mn) 时间，并且使用额外的 O(mn) space。构建完成后，您可以使用索引高效地查询特定的 h-l 序列。

Solve this matching with exponential running time in brute force manner