Module: 前缀函数、Z函数


Problem

5 /10


Z函数

Theory Click to read/hide

Z-函数
Z-function from string S - 数组Z，其中每个元素都是Z [i ]等于字符串S中从位置i开始的子串的最长前缀，也是整个字符串的前缀>Z。 Z 函数在位置零处的值通常为零或整个字符串的长度。
难度
O(|S| ^ 2) 或O(|S|)。
 
前缀函数来自字符串S - 数组P，其中P[i]的每个元素等于最长的后缀字符串S中位置i开始的子串，也是整个字符串S的后缀。 P-function 在位置零处的值通常为零或整个字符串的长度。 
难度
O(|S| ^ 2) 或O(|S|)。
 
尝试实现Z函数和prefix函数 for O(|S| ^ 2) .

Problem

给出了两个字符串 - S 和 T。您的任务是显示字符串 T 中字符串 S 的第 i 前缀出现的次数。

输入
第一行包含k——查询的数量(\(k <= length( S)\)), string 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