#P3172. [Tjoi2013]单词

[Tjoi2013]单词

[TJOI2013] 单词

题目描述

小张为毕业设计读论文。论文由 NN 个单词依次组成。对每个输入单词,他想知道它在论文中出现了多少次。

一次出现是指在某一个输入单词内部找到一段与待查单词完全相同的连续字符。不同的起始位置可以重叠。出现不能跨越两个输入单词的边界,输入中重复出现的单词也分别计入论文。

输入格式

第一行是一个整数 NN。

接下来 NN 行,每行有一个由小写英文字母组成的非空单词。

输出格式

输出 NN 行,第 ii 行输出第 ii 个输入单词在论文中的出现总次数。

样例

3
a
aa
aaa
6
3
1

aa 在 aa 中出现一次,在 aaa 中相互重叠地出现两次,共三次。

数据范围

对于 30%30\% 的数据,单词总长度不超过 10310^3。对于全部数据,1≤N≤2001\le N\le 200,单词总长度不超过 10610^6。