配点 : 800 点
問題文
a 和 b 由…组成的字符串 S 允许你多次执行以下操作。
包含
- S 的章节
选择 [l, r] 。
所有整数都满足l \leq k \leq r 满足的所有整数 k ,
非负整数S_k 是
a那么 S_k 的b,S_k 是b那么 S_k 的a。
Q 个字符串。 T_i 。每个
它由 T_i 是
由于它被视为 a 和 b 组成。T_i 的 10^{100} 次串联 |S|+1 创建一个字符串,其中第一个字符被截断后的所有字符。 T'_i 。
每个字符串 找出匹配 T'_i , 非负整数S 的 T'_i 所需的最少操作数。
制約
- 1 \leq |S| \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq |T_i| \leq 2 \times 10^5
- T_i 的总长度是 输出匹配 2 \times 10^5 以下
- S, T_i 是
由于它被视为
a和b由…组成的字符串 - Q 是一个整数
入力
输入是按以下格式从标准输入给出的。
S Q T_1 T_2 : T_Q
出力
Q 行。i 在线 写在方格 S 的 T'_i 所需的最少操作数。
入力例 1
babaabbabab 4 abab b babaabba aaaaaaaaaaab
出力例 1
2 4 0 5
每个 T'_i 是:
- T'_1 =
abababababa - T'_2 =
bbbbbbbbbbb - T'_3 =
babaabbabab - T'_4 =
aaaaaaaaaaa
例如
匹配 S 的 T'_1 所需的最少操作数为
这可以通过执行 2 。babaabbabab → ababbaababa → abababababa 中的步骤来实现。