Module: Chức năng tiền tố, chức năng Z


Problem

2 /10


chức năng tiền tố

Theory Click to read/hide

Sau khi tối ưu hóa chức năng tiền tố (để biết chi tiết tại đây ), chúng tôi nhận được thuật toán cuối cùng với tiệm cận O(n):

vector<int> tiền tố_hàm (chuỗi s) {
int n = (int ) s.length();
vector<int>pi(n);
cho (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
trong khi (j > 0 && s[i] != s[j])
j = pi[j-1];
nếu (s[i] == s[j]) ++j;
pi[i] = j;
}
trả vềpi;
}

Problem

Cho một chuỗi không rỗng S có độ dài N không vượt quá \(10^6\). Chúng ta sẽ giả định rằng các phần tử của chuỗi được đánh số từ 1 đến N.
 
Đối với mỗi vị trí của ký tự i trong chuỗi, chúng ta sẽ quan tâm đến chuỗi con kết thúc tại vị trí đó và khớp với một số phần đầu của toàn bộ chuỗi. Nói chung, sẽ có một số chuỗi con như vậy, ít nhất là hai. Cái dài nhất trong số chúng có độ dài i, chúng tôi sẽ không quan tâm đến nó. Và chúng ta sẽ quan tâm đến chuỗi dài nhất trong số các chuỗi con còn lại như vậy (lưu ý rằng một chuỗi con như vậy luôn tồn tại — trong trường hợp cực đoan, nếu không tìm thấy gì khác, thì một chuỗi con trống sẽ làm được).
 
Giá trị của hàm tiền tố \(\pi[i]\) sẽ là độ dài của chuỗi con này.
 
Hàm tiền tố được sử dụng trong các thuật toán xử lý chuỗi khác nhau. Đặc biệt, nó có thể được sử dụng để giải quyết nhanh vấn đề tìm kiếm sự xuất hiện của một chuỗi trong một chuỗi khác ("tìm kiếm một mẫu trong văn bản").
 
Bắt buộc đối với tất cả i từ 1 đến N để tính toán \(\pi[i ] \).
 
Đầu vào
Một chuỗi có độ dài N, \(0 < N <= 10^6\), bao gồm các chữ cái Latinh nhỏ .
 
Đầu ra
Xuất số N — các giá trị chức năng tiền tố cho từng vị trí, cách nhau bởi dấu cách.
 

 

Ví dụ
<đầu>

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!

# Đầu vào Đầu ra
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4