4

私はサフィックスの範囲を構築しようとしています

文字列があれば"catalog""catalyst" "ban" "bany"

すると接尾辞木は次のようになります

                            .
                           / \
                          c   b
                         /     \
                        a       a
                       /         \
                      t           n
                     / \         / \        
                    a   a       $   y 
                   /     \         / \
                  l       l       $    $
                 /         \
                o           y         
               /             \
              g               s
             / \               \
            $   $               t
                                /\
                               $   $

各文字列のサフィックス範囲を今すぐ見つけたいと思います。文字列「Cat」を取得すると、「cat」がプレフィックスであるすべてのサフィックスを囲む範囲が得られるはずです。各文字列を区切るためにセンチネルを使用する必要があります..「$」の場合があります

誰かがc++を使用してこれを見つけるための最良の方法を私に提案できますか？どんな参考文献も役に立ちます。ありがとうございました

4

4 に答える 4

2

私の最初の答えよりもはるかに簡単な答え。std :: set ofstringsがあります：

typedef std::set<std::string>::iterator iter_type;
std::set<std::string> data;

そして、イテレータのペアを返すfind（）という名前の関数。最初のイテレータはプレフィックスに一致する文字列の先頭を指し、最後のイテレータはプレフィックスに一致する最後の文字列の1つ後です。10000個の文字列がある場合、これはそのうちの約26個をチェックするだけで済みます。

std::pair<iter_type, iter_type> find(std::string substr) {
   std::pair<iter_type, iter_type> r;
   r.first = data.lower_bound(substr);
   substr[substr.size()-1]++; //I'm assuming substr is at least one character
   r.second = data.upper_bound(substr);
   return r;
}

次に、データがロードされた後、find（...）関数を呼び出すだけで、必要な文字列を指すイテレータのペアが返されます。これらを任意の標準アルゴリズムへの入力として使用することも、何でも行うことができます。

int main() {
    data.insert("catalog");
    data.insert("catalyst");
    data.insert("ban");
    data.insert("bany");
    //find the region of strings beginning with "cat"
    std::pair<iter_type, iter_type> range = find("cat");
    //display them all
    for(iter_type i=range.first; i!=range.second; ++i)
        std::cout << *i << '\n';
}
于 2011-08-23T19:37:39.110 に答える
1

解決策1：スペース効率の良いUse Trieデータ構造（1文字は1ノード、1ノードは26の異なるノードを指すことができます）指定されたプレフィックスの最後のノードを見つけます。プレフィックス+「すべてのターミナルノードへのパス」を出力します

解決策2：時間効率が良いのは、最初の3つのプレフィックス文字だけに関心があると言うことです。3D配列を作成する

 vector<string> arr[27][27][27]

入れる 。単語を挿入する場合
：ABCD arr [A] [B] [C] .push_back（ "D"）単語：BBBX arr [B] [B] [B] .push_back（ "X"）

印刷：vector＆a = arr [char1] [char2] [char3] for（string s in a）char1-char2-char3 + s

于 2011-08-23T19:38:31.187 に答える
0

非常によく似た問題を解決するためのアルゴリズムを投稿しました。この質問を解決するための適切なデータ構造はありますか？。まず、次のようなノードの接尾辞木を作成します

class node { //create a prefix node type
    node & operator=(const node & b); //UNDEFINED, NO COPY
    node & operator=(const node && b); //UNDEFINED, NO COPY
    node * next[27];  // pointers to nodes of the next letter (27th letter is $)
public:
    node(); 
    ~node();
    void add(char* mystring);
    void find(char* mystring, 
        std::vector<std::pair<int, std::string>>& out, 
        std::string sofar="");
}root;

そしてそれを埋めます。次に、「cata」のすべてのサブストリングを見つけるために、「cata」の文字に従ってツリーを反復処理します（root [3]-> [0]-> ['t'-'a'？]-> [ 0]）、文字列を追跡しますsofar。の終わりに達するmystringと、部分文字列に一致する子だけでなく、各子を再帰的に下に移動し、「end」（文字27）が見つかった場合は、にプッシュsofarしoutます。次に、単に戻り、out「cata」で始まるすべての完全な文字列を保持します。

于 2011-08-23T19:19:31.917 に答える
0

これが、おそらく最も簡潔な答えです。:)

set<string> s;
string word = "ABC"
//Inserts.
// e.g. s.insert("ABCD");

for(set<string>::iterator it=s.begin();it!=s.end();++it)
    if(!(*it).compare(0,word.size(),word))
        cout<<*it<<endl;

テスト済みのコード！：P

于 2011-08-24T17:53:37.997 に答える