C++中的字符串和索引

Question

我正在學習C++並且在線處理一些挑戰。然而，似乎大部分「正常」挑戰我總是陷入困境。我不確定自己是否缺乏知識，或者只是過度認知。無論如何，如果有人能幫助我，我將不勝感激。

我想要做這個挑戰： 例如，我的輸入是一個數字「N」，之後我將不得不輸入「N」個字符串。

然後，我必須找到每個字符串typen的最小量的前綴，並確保它們不重複。例如，字符串「stackoverflow」有許多前綴：s，st，sta，stac，stack，stacko，stackov，stackove，stackover，stackoverf，stackoverfl，stackoverflo，stackoverflow。

所有這些都是stackoverflow的前綴。所以，如果我們有另一個字符串「standup」，我們必須輸入stackoverflow - stac，因爲已經存在stup，所以它將成爲standup的標準。

在此先感謝。

Answer 1

創建樹：（線索？）

讓在此樹的每個節點都有一個最大的26名兒童，每個字母（A-Z）的。

從根到葉的路徑表示一個字符串。

 root 
      \ 
      s 
      | 
      t 
      | 
      a 
      /\ 
      c n 
     /| 
     k d 
     | | 
     o u 
     ... 

只需將所有項目添加到此樹中。

然後，用深度優先搜索處理樹，每當你得到一個只有1個樹葉的節點（你可以跟蹤這些計數）時，打印該字符串到目前爲止並遞增。所以在c和n將只有1葉，所以你會分別打印stac和stan。我不會說上面的方法特別適合於一個更大的C++程序員，但是這裏有一些代碼應該工作：（請原諒C和C++以及其他各種暴行在下面的災難性混合，這是隻是一個超級快速和骯髒的方法）

（link）

#include <string> 
#include <iostream> 
using namespace std; 

class Node 
{ 
    public: 
    int count; 
    Node *(children[26]); // array of pointers 
    Node() { count = 0; for (int i = 0; i < 26; i++) children[i] = NULL; }; 
}; 

void add(char *s, Node &n) 
{ 
    if (*s == 0) // null-terminator 
     return; 
    if (n.children[*s-'a'] == NULL) 
     n.children[*s-'a'] = new Node(); 
    n.count++; 
    add(s+1, *n.children[*s-'a']); 
} 

void print(char *start, char *end, Node &n) 
{ 
    if (n.count == 1) 
    { 
     *end = 0; // null-terminator 
     cout << start << endl; 
     return; 
    } 
    for (int i = 0; i < 26; i++) 
    { 
     if (n.children[i] != NULL) 
     { 
      *end = (char)(i+'a'); 
      print(start, end+1, *n.children[i]); 
     } 
    } 
} 

int main() 
{ 
    char *s = "stackoverflow"; 
    Node root; 
    add(s, root); 
    s = "standup"; 
    add(s, root); 
    char output[1000]; // big buffer 
    print(output, output, root); 
} 

Answer 2

最簡單的版本，我能想到的;

• 按字母順序排列單詞列表。將第二個到最後一個單詞的副本附加到列表中。

• 對於列表中的每個單詞，其唯一前綴是與列表中的下一個單詞相比使其唯一的字母數。

一個例子，stackoverflow，standup，seer。

列表成爲;

seer 
stackoverflow 
standup 
stackoverflow 

seer only requires `se` to be unique as compared to `stackoverflow`. 
stackoverflow requires `stac` to be unique as compared to `standup`. 
standup requires `stan` to be unique as compared to `stackoverflow`. 

完成。