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


Problem

5 /10


تابع Z

Theory Click to read/hide

تابع

Z-
Z-function از رشته S - آرایه Z که هر عنصر آن Z است [i ] برابر است با طولانی ترین پیشوند رشته فرعی که از موقعیت i در رشته S شروع می شود، که همچنین پیشوند کل رشته Z. مقدار تابع Z- در موقعیت صفر معمولاً یا صفر یا طول کل رشته است.
مشکل
O(|S| ^ 2) یا O(|S|).
 
تابع پیشوند از رشته S - آرایه P که هر عنصر آن P[i] برابر است با طولانی‌ترین پسوند رشته فرعی که از موقعیت i در رشته S شروع می شود، که همچنین پسوند کل رشته S است. مقدار P-function در موقعیت صفر معمولاً صفر یا طول کل رشته است. 
مشکل
O(|S| ^ 2) یا O(|S|).
 
سعی کنید تابع Z و تابع پیشوند برای ​​O(|S| ^ 2) را اجرا کنید .

Problem

دو رشته داده شده است - S و T. وظیفه شما نمایش تعداد دفعات پیشوند i-امین رشته S در رشته T است.

ورودی
خط اول شامل k - تعداد پرس و جوها (\(k <= 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!