Module: 접두사 함수, Z 함수


Problem

5 /10


Z 기능

Theory Click to read/hide

Z-함수
Z-함수 문자열 S - 배열 Z, 각 요소는 Z [i ]는 문자열 S의 위치 i에서 시작하는 하위 문자열의 가장 긴 접두어와 동일하며 전체 문자열 Z. 위치 0에 있는 Z 함수의 값은 일반적으로 0이거나 전체 문자열의 길이입니다.
난이도
O(|S| ^ 2)또는 O(|S|).
 
문자열 S - 배열 P의 Prefix 함수, P[i]의 각 요소는 전체 문자열 S의 접미사이기도 한 문자열 S의 위치 < code>i에서 시작하는 부분 문자열. 위치 0에 있는 P-함수의 값은 일반적으로 0이거나 전체 문자열의 길이입니다. 
난이도
O(|S| ^ 2) 또는 O(|S|).
 
O(|S| ^ 2)에 대해 Z 기능 및 접두사 기능을 구현해 보세요. .

Problem

S 및 T의 두 문자열이 제공됩니다. 당신의 임무는 문자열 T에서 문자열 S의 i-번째 접두어의 발생 횟수를 표시하는 것입니다.
<사업부>
입력
첫 번째 줄에는 k - 쿼리 수(\(k <= length( S)\)), 문자열 S< /code> 및 문자열 T. 다음으로, k 요청이 입력되며, 문자열 에서 문자열 S의 i번째 접두어 발생 횟수에 대한 요청입니다. >T.
<사업부>
출력
k 줄의 쿼리 응답을 출력합니다.

 

예
<헤드> <일># <몸>

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!

입력 출력
1
2 알리 발리말리
<사업부>3 <사업부>0 		2
8