3

私はそれを読みました：

txt[1..n]で部分文字列pat[1..m]を検索すると、O（m）時間で解決できます（txtの接尾辞木がO（n）時間で構築された後）。

ただし、各ポイントで、取得するブランチを選択する必要があるため、n-aryツリーの場合と同様に、各ノードで、そのノード内のすべての最大n個のポインターと比較して、取得するブランチを決定する必要があります。これは、どういうわけか、このアルゴリズムの複雑さのn要素をもたらさないでしょうか

それでは、O（m）に部分文字列が含まれているとはどういう意味ですか？

ここで何が欠けていますか？

4

2 に答える 2

5

では、部分文字列が O(m) で見つかると上記でどのように述べていますか?

略して。接尾辞ツリーでの検索の実行時間は、単なる O(m) よりも複雑であることは間違いありません。

ただし、スペース要件をトレードオフすると、実際に O(m) まで高速化できます。各ノードでの検索を O(1) まで下げる必要があり、適切なデータ構造 (配列など) を使用してこれを行うことができます。 ) これにより、各文字の適切なサブツリーが一定時間で得られます。

たとえば、実装に C++ を使用していて、文字 ( char) に 256 の異なる値を含めることができるとします。次に、ノードの実装は次のようになります。

struct node {
    char current_character;
    node* children[256];
};

現在、現在のノードにつながるcurrent_character分岐の文字を参照し、子ノードの配列です。検索中、現在ノード にいて、入力テキストの次の文字が であると仮定します。次に、次のノードを次のように選択します。childrenuc

node* next = u->children[c];
if (next == 0) {
    // Child node does not exist => nothing found.
}
else {
    u = next;
    // Continue search with next …
}

もちろん、これは非常に小さなアルファベット (ゲノム配列の DNA など) に対してのみ実行可能です。ほとんどの一般的なケースでは、サフィックス ツリーの最悪の場合の実行時間は実際に O(m) よりも長くなります。

于 2011-06-08T09:14:38.530 に答える
0

子へのポインターが文字でインデックス付けされた配列にある場合、パターン文字ごとに一定の時間だけが必要です

node = tree root
FOR i in 1..m
   node = child[pat[i]]

したがって、複雑さは O(m) です。

于 2011-06-08T09:12:57.130 に答える