入力：アルゴリズムは、文字列と文字列の接頭間の最長接尾語の長さを見つけるために
あり、長い文字列Sがあり、我々は文字列Sの接頭辞を表した整数Aの配列を持っています以下のようなA[i]は、接頭辞に示しS[0..A[i]]
出力：
戻り0と同じサイズの配列Output[]
S = "ababa"
A[]=[0, 1, 2, 3, 4]
サンプル出力：
Output[]=[1,0,3,0,5]
最もナイーブなアルゴリズムOutput[i]はS[0..A[i]]とS
サンプル入力の最長一致接尾語の長さ私はすべてあります。A[i]は、両方の文字列の末尾からS[0..A[i]]とSの間の文字数に一致します。しかし、このアルゴリズムは、nは元の文字列の長さであるO(n^2)であるS.
質問：
は、事前のプロセスは、文字列のSとは、すぐに全体のために最長の長さのサフィックスを返すことができ、より良いアルゴリズムがありますです入力配列？
に機能性とimplemenationを説明し、いくつかのスライドを見つけることができます。わずかな違いは、Z関数の最初の要素がSの長さに等しくなるように選択されていることです。
、次のように、この問題のためのアルゴリズムであるの文字列のZ-関数を計算するためのアルゴリズムがあります：= Z-関数各IためのS」
：
S = "baabaaa"
A[] = [0,1,2,3,4,5,6]
Output[] should be [0,1,2,0,1,2,7]
S' = "aaabaab"
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S))
あなたが探しているアルゴリズム/データ構造がサフィックスツリーと呼ばれているが、それは、コンピュータサイエンス、接尾辞木（でO(n log n)
の最悪のケースの複雑さもPATツリーと呼ばれたり、以前 でいますフォーム、位置ツリー）は、指定されたテキストの接尾辞のすべてをキーとして持つ の接尾辞を含む圧縮トライであり、テキスト内の位置は です。サフィックスツリーは、特に多くの重要な文字列操作の の高速実装を可能にします。 （wiki）
Hereあなたはこれが逆転した文字列のちょうどZ-functionで詳細
「S [1..A [i]]は何であるべきか説明できますか？ '1'から' A [i] 'までの部分文字列？ – Tim
ご迷惑をおかけしました。 S – pgiitu
の '0 [A] 'から' A [i]'までの部分文字列である 'S [0..A [i]]' @Tim - 位置 '0 'から' A [i] ] 'を' S'で実行します。 –