← 返回题目列表

Codeforces · 1721/E

E. 前缀功能查询

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$,由小写拉丁字母组成。

系统会向您提出 $$$q$$$ 查询:给定另一个由小写拉丁字母组成的字符串 $$$t$$$,执行以下步骤:

1. 连接$$$s$$$ 和$$$t$$$;
2.计算结果字符串$$$s+t$$$的前缀函数;
3. 在 $$$|s|+1、|s|+2、\dots、|s|+|t|$$$ 位置打印前缀函数的值($$$|s|$$$ 和 $$$|t|$$$ 分别表示字符串 $$$s$$$ 和 $$$t$$$ 的长度);
4. 将字符串恢复为 $$$s$$$。

字符串 $$$a$$$ 的前缀函数是序列 $$$p_1, p_2, \dots, p_{|a|}$$$,其中 $$$p_i$$$ 是 $$$k$$$ 的最大值,使得 $$$k < i$$$ 且 $$$a[1..k]=a[i-k+1..i]$$$ ($$$a[l..r]$$$ 表示字符串 $$$a$$$ 中从位置 $$$l$$$ 到位置 $$$r$$$ 的连续子串(含)。换句话说,它是字符串 $$$a[1..i]$$$ 的最长的正确前缀,等于其相同长度的后缀。

输入

第一行包含一个非空字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$),由小写拉丁字母组成。

第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行都包含一个查询:一个非空字符串 $$$t$$$ ($$$1 \le |t| \le 10$$$),由小写拉丁字母组成。

输出

对于每个查询,在位置 $$$|s|+1、|s|+2、\dots、|s|+|t|$$$ 上打印字符串 $$$s+t$$$ 的前缀函数的值。

示例

输入 #1

aba
6
caba
aba
bababa
aaaa
b
forces

输出 #1

0 1 2 3 
1 2 3 
2 3 4 5 6 7 
1 1 1 1 
2 
0 0 0 0 0 0

输入 #2

aacba
4
aaca
cbbb
aab
ccaca

输出 #2

2 2 3 1 
0 0 0 0 
2 2 0 
0 0 1 0 1