Module: プレフィックス機能、Z機能


Problem

2 /10


プレフィックス機能

Theory Click to read/hide

プレフィックス関数を最適化した後 (詳細については こちら )、O(n) 漸近の最終アルゴリズムが得られます。

ベクトル<int> prefix_function (文字列 s) {
int n = (int ) s.length();
ベクトル<int>pi(n);
の (int i=1; i<n; ++i) {
int j = pi[i-1< /スパン>];
その間 (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
円周率を返します。
}

Problem

長さ N が \(10^6\)S が与えられた場合>。文字列の要素には 1 から N までの番号が付けられていると仮定します。
 
文字列内の i 文字の各位置について、その位置で終了し、文字列全体の先頭と一致する部分文字列に関心があります。一般的に言えば、そのような部分文字列はいくつか、少なくとも 2 つ存在します。それらの中で最も長いものは i の長さで、これには関心がありません。そして、残りのそのような部分文字列の中で最も長いものに関心があります (そのような部分文字列は常に存在することに注意してください - 極端な場合、他に何も見つからない場合は、空の部分文字列で十分です)。
 
プレフィックス関数 \(\pi[i]\) の値は、この部分文字列の長さになります。
 
プレフィックス関数は、さまざまな文字列処理アルゴリズムで使用されます。特に、ある文字列が別の文字列に出現する問題をすばやく解決するために使用できます (「テキスト内のパターンを検索する」)。
 
\(\pi[i ] \).
 
入力
長さ N、\(0 < N <= 10^6\) の 1 つの文字列で、小文字のラテン文字で構成されます.
 
出力
N 個の数値を出力 —スペースで区切られた、各位置のプレフィックス関数値。
 

 

例
<頭> <本体>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# 入力 出力
1 アブラカダブラ 0 0 0 1 0 1 0 1 2 3 4