2つの文字列の中で最も短い珍しい部分文字列を見つける必要があります。つまり、2つの文字列がある場合a、そのb最も短い部分文字列の長さを見つける必要があります。ab
接尾辞配列を使用してこの問題を解決するにはどうすればよいですか？
n * lg（n）以下の複雑さで解決する
質問する
5432 次
1 に答える
13
これは、一般化された接尾辞木を使用してO（N）時間で解決できます。
O（N）時間で一般化された接尾辞木を構築した後、幅優先探索を実行し、両方の文字列に属していない最初のノードを見つける必要があります。ルートからこのノードへのパスは、最短の珍しいサブストリングを提供します。
同じことが、2つの入力文字列の一般化された接尾辞配列を使用して、O（N）時間でも実行できます。
LCP配列とともに一般化された接尾辞配列を作成します（または、後で接尾辞配列からLCP配列を作成します）。LCP配列のプレフィックスとして単一のゼロ要素を追加します。接尾辞として別のゼロ要素を追加します。これらのエントリで区切られた1つの文字列のみのサフィックスが存在するように、最小のLCPエントリのペアを見つけます。つまり、LCP配列の線形スキャンを実行して、2つの最小値を抽出する必要がありますが、異なる文字列のサフィックスが表示されるたび、または両方の文字列に属するサフィックスが表示される場合は、両方の最小値を無限大にリセットします。これらのペアの最良のものの大きい方の要素（ペアの大きい方の要素の値が最小）は、最も短い珍しい部分文字列の長さを示します。これが機能するのは、この最小値のペアが、対応するサフィックスツリーの両方の文字列に属していない最初のノード（ルートに最も近い）のすべての子孫を区切るためです。
于 2012-09-26T18:00:49.153 に答える