QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB

# 266. 广义后缀自动机

Statistics

题目描述

给定 $n$ 个由小写字母组成的字符串 $s_1,s_2\cdots s_n$,求本质不同的子串个数。(不包含空串)

输入格式

第一行一个正整数 $n$。

以下 $n$ 行,每行一个字符串,第 $i$ 行表示字符串 $s_{i-1}$。

输出格式

一行一个正整数,表示答案。

样例数据

样例输入

10
orzhy
hyakcts
hyakapio
hyakioi
hyaknoi
hyaknoip
bytheway
therulesforthenextseasonwillbeadjustedsoonsostaytuned
gpofuralswillbeheldonmaytheninethusualtimeuralchampionshiponsiteteamsresultswillbecounted
thewidesiberianolympiadchangedtherulesfortheselectioncontestfromacmtomixedacmmarathonwithvariablescoringsoitcannotbeusedastheopencupstageatthecurrentseasoninnextseasonsthenonacmscoringstagesmaybeconsideredbutmajorlastminutechangesarenotacceptablesothegrandprixofeurasiaatoctthetenthiscancelled

样例输出

47675

子任务

对于所有数据,$1 \leq n \leq 10^5, 1 \leq \sum |S| \leq 10^6$。