单词「TJOI 2013」

#include <bits/stdc++.h>
#define re register
using namespace std;

int ans[1000005];

int n, m, len;
string s[1000005];

struct AC_automaton{
	int ch[1000005][30], fail[1000005], val[1000005], f[1000005], tot;
	vector<int> tag[1000005];
	
	inline int o(char c) { return c - 'a'; } 
	
	inline void insert(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;
	
	inline void getfail() {
		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];
			}
		}
	}
	
	inline void solve(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;
	
	inline void toposort() {
		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]);
		}
	}
	
	inline void getans() {
		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;

int main() {
	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;
	}
	return 0;
}