J - Repeat Strings

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

ab からなる文字列 S があって、以下の操作を好きな回数だけ行うことができます。

  • S の連続する区間 [l, r] を選ぶ。l \leq k \leq r を満たすすべての整数 k に対し、S_ka なら S_kb に、S_kb なら S_ka に置き換える。

Q 個の 文字列 T_i が与えられます。各 T_iab からなります。T_i10^{100} 回連結し |S|+1 文字目以降をすべて切り落とした文字列を T'_i とします。

それぞれの文字列 T'_i に対し、ST'_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_iab からなる文字列
  • Q は整数

入力

入力は以下の形式で標準入力から与えられる。

S
Q
T_1
T_2
:
T_Q

出力

Q 行出力せよ。i 行目には ST'_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

例えば ST'_1 に一致させるために必要な操作回数の最小値は 2 です。babaabbababababbaababaabababababa の手順で達成可能です。