問題一覧 > 通常問題

No.1909 Detect from Substrings

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : chineristACchineristAC / テスター : tokusakuraitokusakurai ramdosramdos
2 ProblemId : 7394 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-08 00:14:08

問題文

英小文字からなる $N$ 個の長さ $M$ の相異なる文字列 $S_i\ (1\le i \le N)$ が与えられます。

英小文字からなる長さ $M+1$ の文字列 $T$ であって、すべての $S_i$ が $T$ の（連続とは限らない）部分文字列となるような $T$ がいくつあるか求めてください。

入力

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
  • $2 \le N \le M $
  • $4 \le NM \le 10^6 $
  • $N,\ M$ は整数
  • $S_i$ は英小文字からなる長さ $M$ の文字列
  • $i\neq j$ ならば $S_i \neq S_j$

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2 3
abc
bcd
出力
1

$T=$abcd とすると $S_i$ はすべて $T$ の部分文字列となります。

サンプル2
入力
4 4
abcd
efgh
ijkl
mnop
出力
0

すべての $S_i$ が部分文字列となるような $T$ は存在しません。

サンプル3
入力
2 2
ab
ba
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。