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

我正在处理一些需要大（恒定）位数组的代码。因为它含有大量不变跨度（全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位字节的字符串而不是位串，但是这个问题很有意义任何字符的意义 - 比特，字节或其他）

来源

2012-04-23 R..

我怀疑这是NP难，因为没有办法建立一个命令来处理这些可能会导致DP样解决方案，但我没有知识来证明它。你可能会得到更好的理论或mathoverflow回答 – dfb 2012-04-23 18:40:13

首先，这个问题可以被定义为TSP。我们有一组节点（每个字符串都是一个节点），我们需要找到访问所有节点的路径。字符串x和y之间的距离被定义为len（xy）+ len（y），其中xy是具有x和y并且以x开头的最佳字符串（例如，x = 000111，y = 011100，xy = 0001100 ，距离（x，y）= 8-6 = 2）。注意这也服从三角不等式（距离（x，z）< =距离（x，y）+距离（y，z））。距离是从1到k的整数。此外，距离是不对称的。

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

来源

2012-04-23 18:57:27 ElKamina

我不认为最佳重叠可以确定为只有两个字符串的函数。例如000111和111000.我们可以做000111000或111000111。这将影响其他字符串如何融入更大的字符串 – dfb 2012-04-23 23:25:47

@spinning_plate正是！这就是为什么它是不对称TSP。根据我的定义，xy与yx不同。 – ElKamina 2012-04-24 00:28:10

对不起，错过了那部分 – dfb 2012-04-24 02:46:34

关于你的大的恒定位数组，大段常量，这里有一个替代方法来设计表格供你考虑（我不知道你确切的需求，所以我不能说它是否会帮助或不）。

考虑类似于radix tree。为了便于说明，让我定义get函数：

#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）....虽然它应该仍然非常快。

这里的难点在于设置合适的数据结构很烦人且容易出错。但是你说阵列是恒定的，所以这可能不成问题。

来源

2012-04-23 20:36:21

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

回答

相关问题