#P18945. [Mladen Manev 2021 A1] politics / 删除一段后的前缀支持数

[Mladen Manev 2021 A1] politics / 删除一段后的前缀支持数

删除一段后的前缀支持数

给定小写字母串 ss 和 MM 个小写字母串 p1,…,pMp_1,\ldots,p_M。对于每个 d=1,2,…,Kd=1,2,\ldots,K,从 ss 中删除恰好 dd 个连续字符,得到 s′s'。你可以针对不同的 dd 选择不同的删除位置。

求最多有多少个 pip_i 以 s′s' 为前缀。重复的输入字符串按各自编号分别计数。空串是所有字符串的前缀。

输入格式

第一行字符串 ss;第二行整数 M,KM,K;接下来 MM 行,每行字符串 pip_i。

输出格式

一行 KK 个整数,第 dd 项是删除长度为 dd 的一段后,能够获得的最大支持数。

数据范围

1≤K≤∣s∣≤1051\le K\le |s|\le10^5,1≤∑i∣pi∣≤1051\le\sum_i|p_i|\le10^5。所有字符串非空,仅含小写英文字母。

样例

abcabc
4 4
abba
abcba
abcbc
aab
1 0 2 3

来源与数据说明

2021 年 Dr. Mladen Manev,A1,原题名 politics。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。