指定された文字列の配列からすべての部分文字列を見つけるアルゴリズム

Question

指定された文字列の配列からすべての部分文字列を見つけてグループ化する必要があります。

追加条件：

文字列S1は、文字列S2が含まれている場合は、S1がS3が含まれ、S2は、S4が含まれている - 彼らは一つのグループにする必要がありますすべて。

例：

指定された配列： こんにちは、こんにちはジョン、こんにちは、こんにちはボブ、地獄、こんにちはすべて

結果出力：

グループ1：こんにちは、こんにちは、ジョン、ヘル、

グループ2：こんにちはボブ、こんにちはすべて

Answer 1

• 、各アレイエントリのストリング
• のアレイ上trieビルドトライを歩くと、現在のノードがワードマーク場合、（現在の文字列と同じグループの下に）それを印刷。同じ言葉を何度も印刷することを避けるために、いくつかの簿記をしてください。タイヤを構築するための

時間の複雑さは|wi|が文字列wiの長さがあるO(|w1| + ... + |wn|)あります。文字列の長さの合計で線形です。空間の複雑さは同じ表現によって制限されていますが、共通プレフィックスがたくさんある場合（実際にはどうなるでしょうか）、はるかに低くなります。

クエリステップには、文字列の長さに線形の時間複雑性があります。文字列に対応するブランチをたどるだけです。 （途中で訪れた文字列にマークを付けることもできますし、現在の文字列の前に接頭辞を付けておくこともできます。後でそれらをトラバースしないようにすることもできます。 。さらに下）ここで

はあなたが始めるために構造体です：

typedef struct node_t_ node_t; 
struct node_t_ { 
    node_t c *children[ALPHABET_SIZE]; 
    char kIsLeaf; // set to 1 if represents a word 
    char ch; // character stored in the leaf (redundant) 
} 

の挿入が容易になります。ゼロ以外の文字（空の文字列を表す）を格納するNULL以外の文字で始まるroot。

挿入：

void insert(const char* str) { 
    node_t* current = root; 
    while (*str != '\0') { 
     if (current->children[*str] == NULL) { 
      create new node; 
     } 
     current = current->children[*str++]; 
    } 
    current->kIsLeaf = 1; 
} 

他の手順は非常に類似しています。 Trieは非常にエレガントで、実装が簡単で使いやすいデータ構造です。