文字列グループ化アルゴリズムC＃

Question

C＃の文字列のグループ化アルゴリズムのようなものが必要です。

key|value 

"bla","AAA;BBB;CCC" // ';' is split sign 
"whatever","BBB;DDD;EEE;FF" 
"hmm", "ZZZ,YYY,XXX" 
"foo", "CCC,JJJ,VVV" 
.... 

： 私は日のために試みたと私は怒っ行く前に、私は多分誰かに尋ねるべきではありません:) （なしadjazenctmatrix ^^） 私が何をしているかは、このようなDictonary

何かのデータであります

value1とvalue2のは、それは新しい文字列にグループので、「BBB」が含まれています（？新しい辞書で、キー何でも...カウンタ）

"AAA;BBB;CCC;EEE;FF" (or without distinct to "AAA;BBB;CCC;BBB;DDD;EEE;FF") 

値3は、彼自身のグループ

です

value4 contains "CCC" so group it to the others 
"AAA;BBB;CCC;EEE;FF;JJJ;VVV" (or without distinct to "AAA;BBB;CCC;BBB;DDD;EEE;FF;CCC;JJJ;VVV") 

私はSQLの更新のためにその文字列を必要とする

更新項目設定グループ=のグループ（「」、「」、...）

私はスプリットでそれを行うと参加バー 、この一部の作品： - P

ありがとう

Answer 1

まずデータを整理します。地図keys["bla"] = some_set("AAA", "BBB", "CCC");などがあります。次に、reverse["BBB"] = ["bla", "whatever"]のような逆マップを作成します。両方のマップは元のデータとほぼ同じサイズにする必要があります。ですから、今DSF("bla")を呼び出すことができます

merge = some_set() 
DFS(string key) { 
    if (key in merge) return; // Been here already. 
    merge.insert(key); 
    for (string edge : keys[key]) 
    for (string other_key : reverse[edge]) 
     DFS(other_key) 
} 

：

次は暗黙のグラフ（擬似コード）の上にDFSを行うことができます。返されるときには、"bla", "whatever", ..."とグループに含まれる可能性のある他のキーが含まれていて、keysの文字列を連結して、必要な結果を得ることができます。

キーごとにDFSを呼び出して、各キーが属するすべてのグループ（複雑度O（N^2 * set_op））を取得できます。あるいは、もう一度やり直すのを避けるために、すでに処理したキー（複雑さO（N * set_op））を追跡してください。

ハッシュベースのセット/マップを使用する場合、set_opはO(average string length)です。ツリーベースの構造を使用する場合、set_opはO(logN)です。あなたが非常に長い文字列やたくさんのキーを持っていない限り、これは重要ではありません。