包含给定集合中所有字符串的最优子串

Question

我正在处理一些需要大型（常量）二进制数组的代码。由于它包含大量的常量跨度（全为0或全为1），因此我将其分成了两级表，允许省略重复跨度（无论是常量还是其他），如下所示：

bitn = table2[table1[n/256]+n%256/8]&1<<n%8

此时，table1 中的所有条目都是32的倍数（256位），但我想知道是否可以通过允许 table2 中的跨度重叠来实现显著的节省。因此我的问题是（用抽象形式陈述）：

给定长度为 K 的 N 个字符串 { S_n : n=1..N }，有没有一种有效的方法找到最短的字符串 S，使得每个 S_n 都是 S 的子字符串？

（请注意，由于我可能希望保持我的位数组为8位对齐，所以我特定应用该问题时可能会处理8位字节而不是位字符串，但该问题在任何字符 - 位、字节或其他方面都是有意义的。）

- R.. GitHub STOP HELPING ICE

---

我怀疑这个问题是NP难的，因为没有办法建立一个处理顺序，可能会导致类似于DP的解决方案，但我没有足够的知识来证明它。你可能会在理论或mathoverflow上得到更好的答案。 - dfb

Answer 1

首先，这个问题可以被定义为TSP。我们有一组节点（每个字符串都是一个节点），需要找到访问所有节点的路径。字符串x和y之间的距离定义为len(xy)+len(y)，其中xy是具有x和y的最佳字符串，并以x开头（例如，x=000111，y=011100，xy=0001100，distance(x,y)=8-6=2）。

请注意，这也遵守三角不等式（distance(x,z) <= distance(x,y)+ distance(y,z)）。距离是从1到k的整数。此外，距离是非对称的。

这个版本的TSP被称为（1，B）-ATSP。请参见http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.3439，了解这种问题的分析和近似解决方案。

- ElKamina

---

我认为仅凭两个字符串无法确定最佳重叠。例如，000111和111000。我们可以选择000111000或111000111。这将影响其他字符串合并到更大字符串的方式。 - dfb

@spinning_plate 没错！这就是为什么它是非对称TSP的原因。根据我的定义，xy与yx不同。 - ElKamina

好的，抱歉，我漏掉了那部分。 - dfb

Answer 2

关于您的大型、常量位数组和大量常量部分，这里有一种备选的设计方式供您考虑（我不知道您的确切需求，所以无法确定它是否有帮助）。

考虑使用类似于基数树的东西。为了方便解释，让我定义一个获取函数：

#define TYP_CONST
#define TYP_ARRAY

struct node {
    unsigned min;
    unsigned max;
    int typ;
    union {
        char *bits;
        int constant;
    } d;
    struct node *left;
    struct node *right;
}

struct bit_array {
    unsigned length;
    struct node *root;
}

int get(struct bit_array *b, unsigned ix)
{
    struct node *n = b->root;
    if (ix >= b->length)
        return -1;
    while (n) {
        if (ix > n->max) {
            n = n->right;
            continue;
        } else if (ix < n->min) {
            n = n->left;
            continue;
        }
        if (n->typ == TYP_CONST)
            return n->d.constant;
        ix -= n->min;
        return !!(n->d.bits[ix/8] & (1 << ix%8));
    }
    return -1;
}

以人类的术语来说，您想要在树中搜索您的位。每个节点负责一定范围的位，您可以通过二进制搜索这些范围来找到所需的范围。

一旦找到您的范围，有两个选项：常量或数组。如果是常量，则只需返回该常量（可以节省大量内存）。如果是数组，则需要在位数组中进行数组查找。

您将拥有O(log n)的查找时间，而不是O(1)……尽管它仍然应该非常快。

困难在于设置适当的数据结构很麻烦且容易出错。但是您说数组是常量，因此可能不会有问题。

- Robert Martin