No.430 文字列検索

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 106
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : りあん🐺☔️⛄️りあん🐺☔️⛄️

4 ProblemId : 1013 / 出題時の順位表

問題文

大文字のアルファベットからなる文字列$S$が1つ与えられる。
次に、$M$個の異なる文字列$C_i$($i$ = $0$, $1$, ... , $M-1$)が与えられる。
文字列$S$のなかに文字列$C_i$が部分文字列としてそれぞれいくつ含まれるか数え合計を答えよ。

入力

$S$
$M$
$C_0$
$C_1$
$ \vdots\ $ 
$C_{M-1}$

文字列$S$は大文字のアルファベットのみからなる。
$1\le 文字列Sの長さ \le 50000=5 \times 10^4$
$M$は正の整数。$1\le M \le 5000=5 \times 10^3$。
$i$番目の文字列$C_i$は大文字のアルファベットのみからなる。
$1\le$ 文字列$C_i$の長さ $\le 10$。
$C_i$は互いにすべて異なる文字列である。

出力

すべての部分文字列の数を答えよ。
最後に改行してください。

サンプル

サンプル1
入力
ABCDABCD
3
A
DA
ABCDABCD
出力
4

文字列「ABCDABCD」の中に文字列「A」は2個含まれます。
文字列「ABCDABCD」の中に文字列「DA」は1個含まれます。
文字列「ABCDABCD」の中に文字列「ABCDABCD」は1個含まれます。
よって、答えは2+1+1=4になります。

サンプル2
入力
YUKICODER
2
X
ABCDEFGHIJ
出力
0

1つも含まれないこともありますよね。

サンプル3
入力
AAAA
4
A
AA
AAA
AAAA
出力
10

サンプル4
入力
ABAACABCAACBABABACBBAC
7
A
C
AA
ABB
ABA
BA
CBBAC
出力
26

提出ページヘ