Module: プレフィックス機能、Z機能


Problem

5 /10


Z関数

Theory Click to read/hide

Z-関数
Z-function 文字列 S から - 配列 Z、その各要素は Z [i ] は、文字列 S 内の位置 i から始まる部分文字列の最長の接頭辞に等しく、文字列 全体の接頭辞でもあります>Z.ゼロ位置の Z 関数の値は、通常、ゼロまたは文字列全体の長さです。
難易度
O(|S| ^ 2) または O(|S|).
 
文字列 S の接頭辞関数 - 配列 P、その P[i] の各要素は、文字列 S 内の位置 < code>i から始まる部分文字列。これは、文字列 S 全体のサフィックスでもあります。 P-function の位置 0 の値は、通常、0 または文字列全体の長さです。 
難易度
O(|S| ^ 2) または O(|S|).
 
Z関数とプレフィックス関数  for O(|S| ^ 2)を実装してみてください.

Problem

S と T という 2 つの文字列が指定されます。あなたのタスクは、文字列 T 内の文字列 S の i 番目のプレフィックスの出現数を表示することです。

入力
最初の行には、k - クエリの数 (\(k <= length( S)\))、文字列 が含まれます。 S と文字列 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