No.430 String Search
タグ : / 解いたユーザー数 481
作問者 :
nmnmnmnmnmnmnm
/ テスター :
りあん
Problem Statement
You are given a string $S$ consisting of uppercase letters.
Next, you are given $M$ distinct strings $C_i$ ($i$ = $0$, $1$, ... , $M-1$).
Count how many times each string $C_i$ is contained in the string $S$ as a substring, and output the total.
Input
$S$
$M$
$C_0$
$C_1$
$ \vdots\ $
$C_{M-1}$
The string $S$ consists only of uppercase letters.
Length of the string: $1\le 文字列Sの長さ \le 50000=5 \times 10^4$
$M$ is a positive integer. $1\le M \le 5000=5 \times 10^3$.
The $i$-th string $C_i$ consists only of uppercase letters.
$1\le$ length of the string $C_i$ $\le 10$.
The strings $C_i$ are all pairwise distinct.
Output
Output the number of all the substrings.
Print a newline at the end.
Sample
Sample 1
Input
ABCDABCD 3 A DA ABCDABCD
Output
4
The string "ABCDABCD" contains the string "A" 2 times.
The string "ABCDABCD" contains the string "DA" 1 time.
The string "ABCDABCD" contains the string "ABCDABCD" 1 time.
Therefore, the answer is 2+1+1=4.
Sample 2
Input
YUKICODER 2 X ABCDEFGHIJ
Output
0
Sometimes none of them are contained at all, you know.
Sample 3
Input
AAAA 4 A AA AAA AAAA
Output
10
Sample 4
Input
ABAACABCAACBABABACBBAC 7 A C AA ABB ABA BA CBBAC
Output
26
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。