#1850. [语言月赛 202511] 太空曼波

[语言月赛 202511] 太空曼波

题目描述

牢大养了 nn 只哈基米,第 ii 只哈基米的名字为小写英文字符串 sis_i。

牢大并不擅长起名,因此,很多名字之间存在关联。如果 sis_i 可以被划分为两段 pi,qip_i, q_i,且满足下列条件:

  • si=concat⁡(pi,qi)s_i=\operatorname{concat}(p_i,q_i),其中 concat⁡\operatorname{concat} 表示拼接
  • pip_i 是 sj(1≤j≤n,j≠i)s_j(1 \le j \le n, j \neq i) 的前缀
  • qiq_i 是 sk(1≤k≤n,k≠i)s_k(1 \le k \le n, k \neq i) 的后缀
  • pi,qip_i,q_i 均不是空串。

:::info[定义:前后缀]{open}

对于字符串 S=S1S2…SnS=S_1S_2\ldots S_n:

  • ∀i∈[1,n]\forall i \in [1, n],S1S2…SiS_1S_2\ldots S_i 是其前缀
  • ∀i∈[1,n]\forall i \in [1, n],SiSi+1…SnS_iS_{i+1}\ldots S_n 是其后缀

例如,字符串 abcd 的前缀有 a、ab、abc、abcd,后缀有 d、cd、bcd、abcd。

:::

则称 sis_i 是一个合成的名字。

请问,nn 只哈基米的名字中,一共有多少是合成的。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行一个字符串 sis_i。

输出格式

输出一行一个正整数,表示合成的名字数目。

样例

4
manbo
manba
nba
abc
1

题目来源:洛谷 B4435