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


Problem

5 /10


وظيفة Z

Theory Click to read/hide

Z وظيفة
Z -الوظيفة من السلسلة S - المصفوفة Z ، كل عنصر منها هو Z [i] يساوي أطول بادئة في السلسلة الفرعية التي تبدأ من الموضع i في السلسلة S ، وهي أيضًا بادئة السلسلة Z . قيمة الدالة Z في الموضع صفر عادةً ما تكون إما صفرًا أو طول السلسلة بأكملها.
صعوبة
O (| S | ^ 2) أو O (| S |) .
& nbsp؛
دالة بادئة من السلسلة S - صفيف P ، كل عنصر منها P [i] يساوي أطول لاحقة في تبدأ السلسلة الفرعية من الموضع i في السلسلة S ، وهي أيضًا لاحقة السلسلة بأكملها S . قيمة الدالة P - عند الموضع صفر هي إما صفر أو طول السلسلة بأكملها. & nbsp؛
صعوبة
O (| S | ^ 2) أو O (| S |) .
& nbsp؛
حاول تنفيذ دالة Z و وظيفة البادئة & nbsp؛ لـ O (| S | ^ 2) .

Problem

تم إعطاء سلسلتين - S و T . مهمتك هي عرض عدد تكرارات البادئة i -th للسلسلة S في السلسلة T .

إدخال
يحتوي السطر الأول على k - عدد الاستعلامات ( \ (k & lt؛ = length (S) \) ) ، السلسلة S والسلسلة T . بعد ذلك ، يتم إدخال طلبات k ، وهو طلب لعدد تكرارات البادئة رقم i للسلسلة S في السلسلة T .

الإخراج
إخراج k سطور من ردود الاستعلام.

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1
2 علي باليمالي
3
0
2
8

time 2000 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!