string - 最大部分文字列検索

Question

ラテン文字の小文字で構成される文字列Sが与えられます。位置i'<iが存在する位置S[i]の最大長L[i]ごとに、s [i'.. i'+ L [i] -1] =s[i。。 i + L[i]-1]。例：s = ababaab、L={0,0,3,2,1,2,1}。時間<O（| S | ^ 2）でやりたい。問題は接尾辞配列で解決されると思いますが、どうすればよいですか？

Answer 1

ZBlock アルゴリズムを見る必要がありますが、このアルゴリズムは少し異なる問題 (i' は常に 0 に等しい) を解決しますが、O(|S|) で実行されます。都合のよいときに変更できるはずです。

動的プログラミングは、部分文字列一致の修正版を使用して O(|S|^2) でこれを解決しますが、そのような解決策を探していないと思います。

Answer 2

あなたが探しているのは「最長の以前の因子」と呼ばれ、これを計算するための2つの接尾辞配列アルゴリズムを使用したCrochemoreとIlieによる論文が実際にあります。良いニュースは、どちらも線形時間であることです。2 番目のアルゴリズムは Lcp テーブルを使用しており、少し簡単に見えます。