#include<bits/stdc++.h> #define re register usingnamespacestd;
int ans[1000005];
int n, m, len; string s[1000005];
structAC_automaton{ int ch[1000005][30], fail[1000005], val[1000005], f[1000005], tot; vector<int> tag[1000005]; inlineinto(char c){ return c - 'a'; } inlinevoidinsert(string str, int id){ int x = 0; for (re int i = 0; i < str.size(); i++) { if (!ch[x][o(str[i])]) { ch[x][o(str[i])] = ++tot; } x = ch[x][o(str[i])]; } tag[x].push_back(id); } queue<int> q; inlinevoidgetfail(){ while (!q.empty()) q.pop(); for (re int i = 0; i < 26; i++) if (ch[0][i]) q.push(ch[0][i]); while (!q.empty()) { int x = q.front(); q.pop(); for (re int i = 0; i < 26; i++) { if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]); else ch[x][i] = ch[fail[x]][i]; } } } inlinevoidsolve(string str){ int now = 0; for (re int i = 0; i < str.size(); i++) { now = ch[now][o(str[i])]; val[now]++; } } int in[1000005], b[1000005], cnt; inlinevoidtoposort(){ while (!q.empty()) q.pop(); for (int i = 1; i <= tot; i++) { in[fail[i]]++; } for (int i = 0; i <= tot; i++) { if (!in[i]) q.push(i); } while (!q.empty()) { int x = q.front(); q.pop(); b[++cnt] = x; in[fail[x]]--; if (!in[fail[x]]) q.push(fail[x]); } } inlinevoidgetans(){ toposort(); //拓扑排序完后直接累加就可以了 for (int i = 1; i <= cnt; i++) { int x = b[i]; if (x != 0) val[fail[x]] += val[x]; } for (int i = 0; i <= tot; i++) { for (int j = 0; j < tag[i].size(); j++) { ans[tag[i][j]] += val[i]; } } } } T;
intmain(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (re int i = 1; i <= n; i++) { cin >> s[i]; T.insert(s[i], i); } T.getfail(); for (re int i = 1; i <= n; i++) { T.solve(s[i]); } T.getans(); for (re int i = 1; i <= n; i++) { cout << ans[i] << endl; } return0; }