1

文字列 ' ' に対してアルゴリズムを実行してAEKEAAEKEAAEKEA$、少なくとも 3 回出現する最長の部分文字列を探している場合、サフィックス ツリーのすべてのノードに最大 2 つの分岐があるとしたら、どうすればよいでしょうか?

正しい結果は部分文字列 ' AEKEA' です。

ツリーは、オンラインのサフィックス ツリー ビルダーで簡単に確認できます。

ウィキペディの説明に従っただけです：

「少なくともk回出現する最長の部分文字列を見つける問題は、最初にツリーを前処理して各内部ノードの葉の子孫の数を数え、次に少なくともk回の子孫を持つ最も深いノードを見つけることによって見つけることができます。」

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

ありがとうございました。

4

1 に答える 1

3

私はそのウェブサイトが正しいとは思わない。サフィックスツリーで「AEKEAAEKEAAEKEA」を実行すると、次のツリーが表示されます。

└── (0)
    ├── (27) $
    ├── (6) A
    │   ├── (26) $
    │   ├── (16) AEKEA
    │   │   ├── (17) $
    │   │   └── (7) AEKEA$
    │   └── (18) EKEA
    │       ├── (19) $
    │       └── (8) AEKEA
    │           ├── (9) $
    │           └── (1) AEKEA$
    ├── (4) E
    │   ├── (24) A
    │   │   ├── (25) $
    │   │   └── (14) AEKEA
    │   │       ├── (15) $
    │   │       └── (5) AEKEA$
    │   └── (20) KEA
    │       ├── (21) $
    │       └── (10) AEKEA
    │           ├── (11) $
    │           └── (2) AEKEA$
    └── (22) KEA
        ├── (23) $
        └── (12) AEKEA
            ├── (13) $
            └── (3) AEKEA$

この分岐からわかるように、3 回出現する最長の部分文字列が見つかりました。

└── (0)
    ├── (27) $
    ├── (6) A
    │   ├── (26) $
    │   ├── (16) AEKEA
    │   │   ├── (17) $
    │   │   └── (7) AEKEA$
    │   └── (18) EKEA
    │       ├── (19) $
    │       └── (8) AEKEA
    │           ├── (9) $
    │           └── (1) AEKEA$
于 2012-06-08T13:05:31.867 に答える