3633: 前缀(第二轮03)
题目描述
牛牛有一个S串,S串仅由 26 个小写英文字母组成，他现在将S串进行了无限次的 复制扩展成了一个无线循环串。
例如一开始S = "abc"，那么牛牛就会将其变为 "abcabcabc. . . "
若某个字符串保留其原本字符出现的顺序，并且按照顺序取出若干个字符。可以 不连续，可以不取。
我们称取出的这若干个字符连成的字符串为一个子序列。
若连续取出某个字符串的前k个字符，组成一个子串，我们称该字符串为原串长 度为k的前缀。
对于一个字符串t，若某字符串的至少一个子序列为t。则称它是一个“含t序列串” 牛牛想要知道对于给定的t，他想要知道S的一个最短前缀满足它是一个“含t序列 串”，它的长度有多长？
由于答案可能非常大，所以他要求你输出答案对 998244353 取余数后的结果即 可。
特别的， 如果s串不存在任何一个前缀满足他是一个“含t序列串”， 请输出"-1"表 示无解。
t串中除了26 个英文字母以外还会出现"*"，表示一个通配符。统配符可以视为任 意字母。
例如循环S串为"abcabcabcabc. . . "， t串为"a * ca"时，最短含t序列前缀长 4。而 当t串为"a ** ca" 时，最短含t序列前缀长 7。
除此之外， 牛牛输入的t串还可能非常非常长，最长可以达到 10^{10^5}这么长。
所以他想了一种压缩方法，来快速读入 t 串。
具体来说，它输入的 t 串中除了"*"和 26 个小写英文字母以外，还会跟有一些正 整数。
在读入字符串时，这些数字表示它前面字母或者"*"重复的次数。 例如 a5bc*3，表示"aaaaabc***"。输入的正整数不含前导 0。
输入
第一行输入一个仅包含 26 个小写英文字母的字符串s 第二行输入一个正整数n表示， t串的数目。
接下来输入n行
再输入一行一个字符串t，表示压缩后的查询串。查询串仅包含 26 个小写英文字 母，星号'*'，以及数字。
输出
对于每一个查询，如果至少存在一个 s 的前缀满足“最短含 t 序列串”的定义，请 输出 s 的最短含 t 序列前缀的长度对 998244353 取余数后的结果。
否则请输出"-1"表示无解。
样例输入 复制
abc 3
a*ca
a**ca
a*2ca
样例输出 复制
4
7
7提示
【样例 1 输入】
abc 3
a*ca
a**ca
a*2ca
【样例 1 输出】
4
7
7
【样例 1 解释】
S 串为:abcabcabcabcabc....
包含 a*ca 作为子序列的最短前缀为 abca。
包含 a**ca 作为子序列的最短前缀为 abcabca。 a*2ca 表述的 T 串和 a**ca 等价。
【样例 2 输入】
nowcoder 2
o1000000000000000000000000000000000000000000000000000000000000
winterzz1
【样例 2 输出】
110162207
-1
【样例 2 说明】
最短含t前缀长度为 3
999999999999999999999999999999999999999999999999999999999997 ， 该 数对 998244353 取余数的结果为 110162207
【数据范围】
对于前 10%的测试数据保证1 ≤ n ≤ 100, 1 ≤∣ s ∣, ∣ t ∣≤ 10且 t 串中不包含数字以 及’*’。
对于前 20%的测试数据保证1 ≤ n ≤ 100, 1 ≤∣ s ∣, ∣ t ∣≤ 10且 t 串中不包含数字 。 对于前 30%的测试数据保证1 ≤ n ≤ 1000, 1 ≤∣ s ∣, ∣ t ∣≤ 1000 且 t 串中不包含数 字。
对于前 60%的测试数据保证1 ≤ n ≤ 105, 1 ≤∣ s ∣≤ 104, 1 ≤∣ t ∣≤ 105 且 t 串中 的数字值域范围在[1, 109]内。
对于前 100%的测试数据保证1 ≤ n ≤ 105, 1 ≤∣ s ∣≤ 104, 1 ≤∣ t ∣≤ 105, ∑ ∣ t ∣≤
106 且 t 串中的数字值域范围在 10^{10^5}内。
注意， |t|仅表示输入时的压缩串的长度，不代表解压缩后的长度，解压后t 串的 长度最长可以达到 10^{10^5}。