3002. 最终之作与后缀自动机

【问题描述】

喜大普奔,某科学的一方通行马上就要开播了,最终之作觉得自己是强能力者有些不满足,所以她去打ACM了,但是第一道题就把她难住了,题目如下。

有一些字符串按照顺序输入,对每个串的子串查询与前面多少个字符串相等。

【输入形式】

第一行一个整数n,表示接下来有多少个字符串,接下来有n行,每行一个字符串s,表示按照顺序输入的字符串,其中1<=n<=1e4,len(s)<10。
【输出形式】

输出一个整数ans,表示结果。
【样例输入】

5

10000

1000000

15

150

1551


【样例输出】

3


【样例说明】

ans=0。

10000没有前一个串。

1000000的子串有10000包含前面的10000,ans++。

15的子串是1,5,15,没有前面的10000,1000000。

150的子串包含15,ans++。

1551的子串包含15,不包含150,ans++

ans=3。

TIM鍥剧墖20190622032649.jpg

难度等级: 0
总通过次数: 6
总提交次数: 274