14

wiki による最長共通部分文字列の問題は、サフィックス ツリーを使用して解決できます。ウィキ
から：

文字列の集合の最長の共通部分文字列は、文字列の一般化されたサフィックス ツリーを構築し、その下のサブツリー内のすべての文字列から葉ノードを持つ最も深い内部ノードを見つけることによって見つけることができます。

わかりません。
例: 私が持っている場合:
ABCDEそしてXABCZ
サフィックスツリーは (XABCZスペースのために省略されたいくつかのブランチ):
ここに画像の説明を入力

最長の一般的な部分文字列はABCそうではありませんが、wiki の説明がここでどのように役立つかわかりません。
ABCリーフ ノードを持つ最も深い内部ノードではありません。
これがどのように機能するかを理解するのに役立ちますか?

4

2 に答える 2

8

前に言われたように、あなたの木は正しくありません。

これは、コードで「ABCDE$XABCZ」を実行したときに得られるものです。

接尾辞木コード：

String = ABCDE$XABCZ$
End of word character 1 = $
└── (0)
    ├── (20) $
    ├── (22) ABC
    │   ├── (15) DE$
    │   └── (23) Z$
    ├── (24) BC
    │   ├── (16) DE$
    │   └── (25) Z$
    ├── (26) C
    │   ├── (17) DE$
    │   └── (27) Z$
    ├── (18) DE$
    ├── (19) E$
    ├── (21) XABCZ$
    └── (28) Z$

（コンパクトな）接尾辞ツリーで、すべての文字列からリーフノードを持つ最も深い内部ノードを見つける必要があります。同じ深さに複数のノードがある場合は、そのノードによって表される文字列の長さを比較する必要があります。つまり、ABC、BC、およびCはすべて同じ深さであるため、ABC、BC、およびCの文字列の長さを比較して、どちらが長いかを確認する必要があります。明らかにABCです。

サフィックストライコード：

└── null
    ├── A
    │   └── B
    │       └── C
    │           ├── D
    │           │   └── (E) ABCDE
    │           └── (Z) ABCZ
    ├── B
    │   └── C
    │       ├── D
    │       │   └── (E) BCDE
    │       └── (Z) BCZ
    ├── C
    │   ├── D
    │   │   └── (E) CDE
    │   └── (Z) CZ
    ├── D
    │   └── (E) DE
    ├── (E) E
    ├── X
    │   └── A
    │       └── B
    │           └── C
    │               └── (Z) XABCZ
    └── (Z) Z

（コンパクトではない）接尾辞トライで、すべての文字列からリーフノードを持つ最も深い内部ノードを見つけます。

それが役に立てば幸い。

于 2012-06-12T21:16:57.937 に答える
4

サフィックス ツリーを実際に描画したわけではありません。適切に行っていれば、ルートで可能なすべての文字を 1 回しか取得できません。ツリーは、単一の文字が複数の接尾辞を持つことができる場合にのみ分割されます。これにより、共通の部分文字列がツリー内で強制的にまとめられ、検索可能になります。

于 2012-06-12T20:28:04.157 に答える