/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
文字列 S が与えられます。また、高橋君は次の操作を 0 回以上行うことが出来ます。
- 1 \leq i \leq |S| なる整数 i を選び、S の i 文字目を
*に変える。
高橋君の目的は、S の部分文字列として N 個の文字列 T_1,T_2,\ldots,T_N がいずれも現れないようにすることです。
これを達成するために必要な操作の回数の最小値を求めてください。
制約
- 1 \leq |S| \leq 5 \times 10^5
- 1 \leq N
- N は整数
- 1 \leq |T_i|
- \sum{|T_i|} \leq 5 \times 10^5
- i \neq j ならば T_i \neq T_j
- S, T_i は英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S N T_1 T_2 \vdots T_N
出力
答えを出力せよ。
入力例 1
abcdefghijklmn 3 abcd ijk ghi
出力例 1
2
i として 1 と 9 を選んで操作をすると S は *bcdefgh*jklmn となり、abcd、ijk、ghi がいずれも部分文字列として現れなくなります。
入力例 2
atcoderbeginnercontest 1 abc
出力例 2
0
操作をする必要がありません。
入力例 3
aaaaaaaaa 2 aa xyz
出力例 3
4
Score : 600 points
Problem Statement
You are given a string S. Takahashi may perform the following operation 0 or more times:
- Choose an integer i such that 1 \leq i \leq |S| and change the i-th character of S to
*.
Takahashi's objective is to make S not contain any of N strings T_1,T_2,\ldots,T_N as a substring.
Find the minimum number of operations required to achieve the objective.
Constraints
- 1 \leq |S| \leq 5 \times 10^5
- 1 \leq N
- N is an integer.
- 1 \leq |T_i|
- \sum{|T_i|} \leq 5 \times 10^5
- T_i \neq T_j if i \neq j.
- S and T_i are strings consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S N T_1 T_2 \vdots T_N
Output
Print the answer.
Sample Input 1
abcdefghijklmn 3 abcd ijk ghi
Sample Output 1
2
If he performs the operation twice by choosing 1 and 9 for i, S becomes *bcdefgh*jklmn; now it does not contain abcd, ijk, or ghi as a substring.
Sample Input 2
atcoderbeginnercontest 1 abc
Sample Output 2
0
No operation is needed.
Sample Input 3
aaaaaaaaa 2 aa xyz
Sample Output 3
4