Module: تابع پیشوند، تابع Z


Problem

2 /10


تابع پیشوند

Theory Click to read/hide

پس از بهینه سازی تابع پیشوند (برای جزئیات اینجا)، الگوریتم نهایی را با مجانبی O(n) بدست می آوریم:

ایجاد شد 

بردار<int> prefix_function (رشته ها) {
int n = (int ) s.length();
بردار<int>pi(n);
برای (int i=1; i<n; ++i) {
int j = pi[i-1< /span>]؛
در حالی که (j > 0 && s[i] != s[j])
j = پی[j-1];
اگر (s[i] == s[j]) ++j;
pi[i] = j;
}
بازگشتpi;
}

Problem

با توجه به یک رشته غیر خالی S که طول آن N از \(10^6\) فرض می کنیم که عناصر رشته از 1 تا N شماره گذاری شده اند.
 
برای هر موقعیت از کاراکتر i در رشته، ما به رشته فرعی که به آن موقعیت ختم می‌شود و با ابتدایی از کل رشته مطابقت دارد، علاقه مند خواهیم بود. به طور کلی، چندین زیررشته، حداقل دو رشته وجود خواهد داشت. طولانی ترین آنها دارای طول i است، ما به آن علاقه ای نخواهیم داشت. و ما به طولانی ترین زیررشته های باقیمانده علاقه مند خواهیم بود (توجه داشته باشید که چنین زیررشته ای همیشه وجود دارد &mdash؛ در حالت شدید، اگر چیز دیگری یافت نشد، یک زیررشته خالی انجام می شود).
 
مقدار تابع پیشوند \(\pi[i]\) طول این رشته فرعی خواهد بود.
 
تابع پیشوند در الگوریتم های مختلف پردازش رشته ای استفاده می شود. به ویژه، می توان از آن برای حل سریع مشکل یافتن وقوع یک رشته در رشته دیگر استفاده کرد ("جستجوی یک الگو در متن").
 
برای محاسبه \(\pi[i برای همه i از 1 تا N لازم است ] \).
 
ورودی
یک رشته به طول N، \(0 < N <= 10^6\)، متشکل از حروف کوچک لاتین
 
خروجی
خروجی N اعداد — مقادیر تابع پیشوند برای هر موقعیت، جدا شده با فاصله.
 

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4

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!