#H1001. 【模板】字典树 1

【模板】字典树 1

题目描述

给出 nn 个仅由小写字母组成的字符串,请你求出这些字符串中一共出现了几种不同的字符串。

输入格式

第一行一个整数 nn

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

输出格式

一行一个整数表示一共出现过的字符串数量。

5
aba
aba
ababa
ababa
abababa
3

说明

一共出现了三种不同类型的字符串: abaababaabababa

数据范围

  • Subtask 1(50pts, 1000ms):n105\texttt{Subtask 1(50pts, 1000ms):} n \le 10^5
  • Subtask 2(50pts, 300ms):n=106\texttt{Subtask 2(50pts, 300ms):} n = 10^6

对于 100%100\% 的数据,n1, 字符串长度4×106n \ge 1,~\sum \text{字符串长度} \le 4 \times 10^6

卡掉了使用 O2 优化的 C++ set<string> 方法,较低效的语言可能无法通过此题,建议 C++ 选手使用较快的输入方式并使用带 O2 的语言提交。