c - 包含给定集合中的所有字符串作为子字符串的最佳字符串

Question

我正在处理一些需要大(常量)位数组的代码。由于它包含较大的常量跨度(全 0 或全 1)，我将其分成两级表，允许省略重复跨度(常量或其他)，如:

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

此时，table1 的条目都是 32(256 位)的倍数，但我想知道是否可以通过允许 table2 中的跨度来实现显着的节省交叠。所以我的问题是(以抽象形式陈述):

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

(请注意，因为我可能想让我的位数组保持 8 位对齐，所以我对该问题的特定应用可能是处理 8 位字节的字符串而不是位串，但是这个问题在任何情况下都是有意义的字符感 - 位、字节或其他。)

Answer 1

首先，这个问题可以表述为 TSP。我们有一组节点(每个字符串都是一个节点)，我们需要找到访问所有节点的路径。字符串 x 和 y 之间的距离定义为 len(xy)+len(y)，其中 xy 是同时具有 x 和 y 且以 x 开头的最佳字符串(例如 x=000111、y=011100、xy=0001100 , 距离(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对此类问题的分析和近似解。