H - 404 Chotto Found
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
ちょっとしか見つかりませんでした
問題文
N 個の文字列 S_1, S_2, \dots, S_N が与えられます。空でない文字列 T であって、以下の条件を満たすものの個数を求めてください。
- 文字列 S_1, S_2, \dots, S_N のうち、T を (連続する) 部分文字列として含むものはちょうど 1 個である。
制約
- 1 \le N \le 10^5
- 1 \le |S_i| \le 10^6\ (1 \le i \le N)
- \left(\sum_{i=1}^{N} |S_i|\right) \le 10^6
- S_i\ (1 \le i \le N) は英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
2 abc ca
出力例 1
5
T = {}a
の場合を考えると、S_1 = {}abc
と S_2 = {}ca
の 2 個が a
を部分文字列として含むので、条件を満たしません。
T = {}ab
の場合を考えると、S_1 = {}abc
のみが ab
を部分文字列として含むので、条件を満たします。
T = {}d
の場合を考えると、S_1 = {}abc
も S_2 = {}ca
も d
を部分文字列として含まないので、条件を満たしません。
条件を満たす文字列は T = {}b
, ab
, bc
, ca
, abc
の 5 個です。
入力例 2
2 aab aab
出力例 2
0
T = {}ab
の場合を考えると、S_1 = {}aab
と S_2 = {}aab
の 2 個が ab
を部分文字列として含むので、条件を満たしません。
条件を満たす文字列はありません。
入力例 3
1 aba
出力例 3
5
条件を満たす文字列は T = {}a
, b
, ab
, ba
, aba
の 5 個です。
入力例 4
3 tokyoinstituteoftechnology tokyomedicalanddentaluniversity instituteofsciencetokyo
出力例 4
905