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

我正在處理一些需要大（恆定）位數組的代碼。因爲它含有大量不變跨度（全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

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

回答

相關問題