0

ウッコネンのアルゴリズムを理解しています。複数の文字列を含むように拡張する方法に興味があるだけです(特殊文字「$」で終わります)。

文字列 s1(たとえば "abcddefx$") と s2(たとえば "abddefgh$") が与えられた場合、ukkonen のアルゴリズムで通常どおり s1 を挿入する必要があることをどこかで読みました。次に、s2 でツリーをたどります。つまり、ツリーで s2 を検索する必要があります。検索が終了するノード (「ab」、「b」の後) に到達したら、そこからウッコネンのアルゴリズムを再開する必要があります。

この背後にある基本的なロジックを理解しています。しかし、私が興味を持っているのは、古いサフィックス リンクがどうなるのかということです。それらはまだ有効ですか?また、新しいパスを開始するときに、トリプル (active_node,active_length,remainder) が ("ab",0,0 を表すノード) である必要があることについて混乱していますか???

4

1 に答える 1