Module: Fungsi awalan, fungsi Z


Problem

2 /10


fungsi awalan

Theory Click to read/hide

Selepas mengoptimumkan fungsi awalan (untuk butiran di sini ), kami mendapat algoritma akhir dengan asimptotik O(n):

vektor<int> prefix_function (rentetan s) {
int n = (int ) s.length();
vektor<int>pi(n);
untuk (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
sementara (j > 0 && s[i] != s[j])
j = pi[j-1];
jika (s[i] == s[j]) ++j;
pi[i] = j;
}
kembalipi;
}

Problem

Diberi rentetan bukan kosong S yang panjangnya N tidak melebihi \(10^6\). Kami akan menganggap bahawa elemen rentetan dinomborkan daripada 1 hingga N.
 
Untuk setiap kedudukan aksara i dalam rentetan, kami akan berminat dengan subrentetan yang berakhir pada kedudukan itu dan sepadan dengan beberapa permulaan keseluruhan rentetan. Secara umumnya, akan terdapat beberapa subrentetan sedemikian, sekurang-kurangnya dua. Yang terpanjang mempunyai panjang i, kami tidak akan berminat dengannya. Dan kami akan berminat dengan subrentetan terpanjang yang tinggal (perhatikan bahawa subrentetan sedemikian sentiasa wujud — dalam kes yang melampau, jika tiada apa-apa lagi ditemui, subrentetan kosong akan berfungsi).
 
Nilai fungsi awalan \(\pi[i]\) akan menjadi panjang subrentetan ini.
 
Fungsi awalan digunakan dalam pelbagai algoritma pemprosesan rentetan. Khususnya, ia boleh digunakan untuk menyelesaikan masalah mencari kejadian satu rentetan dalam rentetan yang lain dengan cepat ("cari corak dalam teks").
 
Diperlukan untuk semua i daripada 1 hingga N untuk mengira \(\pi[i ] \).
 
Input
Satu rentetan panjang N, \(0 < N <= 10^6\), terdiri daripada huruf Latin kecil .
 
Output
Output N nombor — nilai fungsi awalan untuk setiap kedudukan, dipisahkan dengan ruang.
 

 

Contoh

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!

# Input Output
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4