题目详情题解（0）讨论（0）提交记录（0）

AT_ttpc2023_h.404 Chotto Found

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 NN 个字符串 S1,S2,…,SNS_1, S_2, \dots, S_N。请计算有多少个非空字符串 TT 满足如下条件：

  • 在所有字符串 S1,S2,…,SNS_1, S_2, \dots, S_N 中，恰好有一个字符串包含 TT 作为（连续的）子串。

输入格式

输入以如下格式从标准输入读入。

NN
S1S_1
S2S_2
⋮
SNS_N

输出格式

输出答案。

输入输出样例

  • 输入#1

    2
abc
ca

    输出#1

    5

  • 输入#2

    2
aab
aab

    输出#2

    0

  • 输入#3

    1
aba

    输出#3

    5

  • 输入#4

    3
tokyoinstituteoftechnology
tokyomedicalanddentaluniversity
instituteofsciencetokyo

    输出#4

    905

说明/提示

样例解释 1

考虑 $T = $ a 的情况，$S_1 = $ abc 和 $S_2 = $ ca 这两个字符串都包含 a 作为子串，所以不满足条件。

考虑 $T = $ ab 的情况，只有 $S_1 = $ abc 包含 ab 作为子串，因此满足条件。

考虑 $T = $ d 的情况，$S_1 = $ abc 和 $S_2 = $ ca 都不包含 d 作为子串，所以不满足条件。

满足条件的字符串为 $T = $ b、ab、bc、ca、abc 共 55 个。

样例解释 2

考虑 $T = $ ab 的情况，$S_1 = $ aab 和 $S_2 = $ aab 这两个字符串都包含 ab 作为子串，所以不满足条件。

没有满足条件的字符串。

样例解释 3

满足条件的字符串为 $T = $ a、b、ab、ba、aba，共 55 个。

数据范围

  • 1≤N≤1051 \le N \le 10^5
  • 1≤∣Si∣≤106 (1≤i≤N)1 \le |S_i| \le 10^6\ (1 \le i \le N)
  • (∑i=1N∣Si∣)≤106\left(\sum_{i=1}^{N} |S_i|\right) \le 10^6
  • Si (1≤i≤N)S_i\ (1 \le i \le N) 是仅由小写英文字母组成的字符串。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页