小时候一直不理解为什么老人会呆呆地坐着，望着远方很久很久
少年不会知道自己的勇气意味着什么，他只是在武汉四十度的天气下奋力奔跑。在军训伊始终于成功联系上了导师，一个小时内赶出简历，基于事实发展创造:），既对自身能力惶惶，又隐隐有些期待。我从没想过自己连复读的经历都能拿来利用，当我写上“21年河南大学学前教育专业，复读”时自己都感觉想笑，必要时，人是会连伤疤都当作资本的存在，四食堂的蒸蛋与人心都是琢磨不透的东西。想要得到「我没有逃避」的记忆而进行多串匹配，想到\(AC\)自动机，但是原本的\(AC\)自动机是不能处理相同串的，所以，需要用一个\(tot\)数组统计数量，再跳\(fail\)得到答案，注意手写队列保证有序性
$click$ $for$ $codes$
# include "bits/stdc++.h"
using namespace std;
constexpr int N = 1e6 + 3;
struct AC {
int ch[N][26], fail[N], tot[N], ed[N];
int id_index = 0, trie_index = 0;
void insert(char *str) { // build a trie
int len = strlen(str + 1), u = 0;
for(int i = 1; i <= len; ++i) {
int v = str[i] - 'a'; // str[i] ^ 'a' is wrong here
if(!ch[u][v]) ch[u][v] = ++trie_index;
u = ch[u][v];
++tot[u];
}
ed[++id_index] = u; // note the node corresponding to the end position of each string
}
void build() { // build the Aho-Corasick automation
int q[N], h = 0, t = 0; // here, we wirite the queue ourselves, so that the incoming nodes can be arranged according to the queue order
for(int i = 0; i < 26; ++i) { // start BFS from root 0
if(ch[0][i]) {
q[++t] = ch[0][i];
}
}
while(h < t) {
int u = q[++h];
for(int i = 0; i < 26; ++i) {
if(ch[u][i]) { // if child nodes are included
fail[ch[u][i]] = ch[fail[u]][i]; // set fail: node(child) -> node(fail: parient -> same value)
q[++t] = ch[u][i]; // come with me for a little ride, see the shadows passing by
}
else {
ch[u][i] = ch[fail[u]][i]; // there is no reason to stay, goodbye mama, I'm going sailing tonight
}
}
}
for(int i = trie_index; i; --i) { // transfer the information of child nodes upward, and note that the use of queue ensures the order
tot[fail[q[i]]] += tot[q[i]];
}
}
} AC;
char str[N];
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%s", str + 1);
AC.insert(str);
}
AC.build();
for(int i = 1; i <= n; ++i)
printf("%d\n", AC.tot[AC.ed[i]]);
return 0;
}
