Module: Önek işlevi, Z işlevi


Problem

2 /10


önek işlevi

Theory Click to read/hide

Önek işlevini optimize ettikten sonra (ayrıntılar için burada ), O(n) asimptotikli son algoritmayı elde ederiz:

vektör<int> önek_işlevi (dize s) {
int n = (int ) s.uzunluk();
vektör<int>pi(n);
for (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
dönüşpi;
}

Problem

Boş olmayan, N uzunluğu \(10^6\)S dizisi verildi. >. Dizinin elemanlarının 1 ile N arasında numaralandırıldığını varsayacağız.
 
Dizedeki i karakterinin her konumu için, o konumda biten ve tüm dizenin bir başlangıcıyla eşleşen alt dizeyle ilgileneceğiz. Genel olarak konuşursak, en az iki olmak üzere bu tür birkaç alt dizi olacaktır. En uzunu i uzunluğundadır, bununla ilgilenmeyeceğiz. Ve kalan bu tür alt dizilerin en uzun olanıyla ilgileneceğiz (böyle bir alt dizenin her zaman var olduğuna dikkat edin — aşırı durumda, başka hiçbir şey bulunamazsa boş bir alt dize yeterli olur).
 
\(\pi[i]\) önek işlevinin değeri bu alt dizenin uzunluğu olacaktır.
 
Önek işlevi, çeşitli dizi işleme algoritmalarında kullanılır. Özellikle, bir dizginin başka bir dizgede tekrarını bulma problemini ("metinde bir kalıp arama") hızlı bir şekilde çözmek için kullanılabilir.
 
\(\pi[i]'yi hesaplamak için 1'den N'e kadar tüm i için gereklidir ] \).
 
Giriş
Küçük Latin harflerinden oluşan N, \(0 < N <= 10^6\) uzunluğunda bir dizi
 
Çıktı
Çıktı N sayıları — boşluklarla ayrılmış her konum için önek işlev değerleri.
 

 

Örnekler

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!

# Girdi Çıktı
1 abrakadabra 0 0 0 1 0 1 0 1 2 3 4