algorithm - 最長反復部分文字列の問題

Question

文字列「ABAB」のサフィックス ツリーを作成すると、2 つのノードしか得られません。

ABABとBAB

最長の repeatead 部分文字列 ("AB") は、「少なくとも k 個の子孫を持つ最も深いノード」に配置する必要がありますが、これは私の文字列には当てはまりません。何が問題なのですか?

ありがとう

Answer 1

文字列 ABAB に対してノードが 2 つしかない形式のサフィックス ツリーを使用している場合、引用したアルゴリズムでは直接動作しません。これは、サフィックス ツリーがどのように見えるかでO、ノードを表し$、文字列の末尾をマークするために使用されます。

         O
        / \
       /   \
      B     AB
     /       \
    O         O
   / \       / \
  $  AB$    $  AB$
 /     \   /     \
O       O O       O

ここでの (そして使用しているツリーには欠けている) 重要な機能は、各リーフ ノードが文字列のサフィックスに対応することです。

少なくとも 2 つの葉の子孫を持つ最も深いノードはパス AB にあり (深さは、ルートからそのノードに到達するために必要な部分文字列の長さであり、この場合は 2 です)、これは実際に最も長く繰り返される部分文字列です。