arrays - 特定のサフィックス配列に一致する文字列を見つける方法は?

Question

接尾辞 arrayがあります。どのサフィックス配列が指定された配列と等しくなるか、文字列を取得する方法は?

例えば。この配列を考えてみましょう: [7, 6, 4, 2, 1, 5, 3]. 次に、文字列banana$は私にとって良いことですget_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3]。

Answer 1

制約から有向グラフを作成し、トポロジカル ソートを実行して、結果の順序に従ってノードに文字を割り当てることができます。

不明な文字のノードを、それぞれに 1 つずつ作成することから始めます ( を除く$)。

であるため、最初のエントリは常に配列の長さになります$。これでは何も得られません。

ただし、次のエントリはそれぞれ制約を与えます。

たとえば、2 番目のエントリは配列の長さから 1 を引いた長さなので、他の文字より大きくてはなりません。したがって、このノードから他のノードのそれぞれにエッジを配置します。ただし、配列の長さから 2 を引いた長さの場合、それよりも小さい文字が存在しますが、他のすべての文字よりも小さくなります。接尾辞配列からこの小さい要素を見つけ、そこから最後の文字まで、最後の文字から他のすべての文字まで、などにノードを配置できます。