Module: وظيفة البادئة ، وظيفة Z.


Problem

2 /10


وظيفة البادئة

Theory Click to read/hide

بعد تحسين وظيفة البادئة (للحصول على تفاصيل هنا ) ، نحصل على الخوارزمية النهائية باستخدام O (n) المقاربات: 

المتجه  & lt؛   int   & gt؛  prefix_function (string s) {
 int  n  =  ( int  ) طول () ؛
المتجه  & lt؛   int   & gt؛  بي (ن) ؛
 لـ  ( int  i  = 1 ؛ i  & lt؛  n؛  ++  i) {
 int  j  =  pi [i  - 1 < / span>]؛
 while  (j  & gt؛   0   & amp؛ & amp؛  s [i] ! =  s [j])
j  =  pi [j  - 1 ]؛
 if  (s [i]  ==  s [j])  ++  ي ؛
pi [i]  =  j؛
}
 عودة  بي ؛
}

Problem

إعطاء سلسلة غير فارغة S لا يتجاوز طولها N \ (10 ​​^ 6 \) . سنفترض أن عناصر السلسلة مرقمة من 1 إلى N .
& nbsp؛
لكل موضع للحرف i في السلسلة ، سنكون مهتمين بالسلسلة الفرعية التي تنتهي عند هذا الموضع وتتطابق مع بداية السلسلة بأكملها. بشكل عام ، سيكون هناك العديد من هذه السلاسل الفرعية ، اثنتان على الأقل. أطولها هو i ، لن نهتم بها. وسنكون مهتمين بأطول السلاسل الفرعية المتبقية (لاحظ أن مثل هذه السلسلة الفرعية موجودة دائمًا & mdash ؛ في الحالة القصوى ، إذا لم يتم العثور على أي شيء آخر ، فستعمل سلسلة فرعية فارغة).
& nbsp؛
ستكون قيمة دالة البادئة \ (\ pi [i] \) هي طول هذه السلسلة الفرعية.
& nbsp؛
تستخدم وظيفة البادئة في خوارزميات معالجة السلاسل المختلفة. على وجه الخصوص ، يمكن استخدامه لحل مشكلة العثور على تواجد سلسلة في أخرى بسرعة ("البحث عن نمط في النص").
& nbsp؛
مطلوب لجميع i من 1 إلى N لحساب \ (\ pi [i ] \) .
& nbsp؛
إدخال
سلسلة واحدة بطول N ، \ (0 & lt؛ N & lt؛ = 10 ^ 6 \) ، تتكون من أحرف لاتينية صغيرة .
& nbsp؛
الإخراج
إخراج N أرقام و mdash؛ قيم دالة البادئة لكل موضع ، مفصولة بمسافات.
نبسب ؛

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1 أبراكادابرا 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!