AT_abc362_g [ABC362G] Count Substring Query

[problemUrl]: https://atcoder.jp/contests/abc362/tasks/abc362_g 英小文字からなる文字列 $ S $ が与えられます。 $ Q $ 個のクエリが与えられるので順に処理してください。$ i $ 番目のクエリは以下で説明されます。 - 英小文字からなる文字列 $ T_i $ が与えられる。$ S $ の部分文字列であって、$ T_i $ と一致するものは何通りあるか出力する。ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとする。

N/A

N/A

### 制約 - $ 1\leq\ |S|\leq\ 5\times\ 10^5 $ - $ 1\leq\ Q\leq\ 5\times\ 10^5 $ - $ 1\leq\ |T_i|\leq\ |S| $ - $ \displaystyle\ \sum_{i=1}^Q\ |T_i|\leq\ 5\times\ 10^5 $ - $ S,T_i $ は英小文字列 - $ Q $ は整数 ### Sample Explanation 1 $ S $ の $ l $ 文字目から $ r $ 文字目までの部分文字列を $ S[l:r] $ とします。 - $ 1 $ つ目のクエリについて、$ S $ の部分文字列であって `i` と一致するものは $ S[2:2],S[5:5],S[7:7],S[10:10] $ の $ 4 $ か所です。 - $ 2 $ つ目のクエリについて、$ S $ の部分文字列であって `s` と一致するものは $ S[3:3],S[4:4],S[6:6] $ の $ 3 $ か所です。 - $ 3 $ つ目のクエリについて、$ S $ の部分文字列であって `a` と一致するものは存在しません。 - $ 4 $ つ目のクエリについて、$ S $ の部分文字列であって `is` と一致するものは $ S[2:3],S[5:6] $ の $ 2 $ か所です。 - $ 5 $ つ目のクエリについて、$ S $ の部分文字列であって `missisippi` と一致するものは $ S[1:10] $ の $ 1 $ か所です。