记录

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

const int L = 2e6+5;
const int N = 2e5+5;

int n;
string c;
string s[N];

int Ans[N];

class AC_tree
{
	private:
		struct Node
		{
			int to[26];
			int end;
			int fail;
			int ans = 0;
			void init()
			{
				memset(to,0,sizeof(to));
				fail = 0; end = 0;
			}
		}t[N];
		int in[N] = {};
		const int root = 0;
		int cnt = 0;
		int New() { return ++cnt; }
	public:
		void clear()
		{
			for(int i = 0; i <= cnt; i++)
				t[i].init();
			cnt = 0;
		}
		void add(string s,int id)
		{
			int len = s.size();
			int p = root;
			for(int i = 0; i < len; i++)
			{
				if(t[p].to[s[i]-'a'] == 0) t[p].to[s[i]-'a'] = New();
				p = t[p].to[s[i]-'a'];
			}
			t[p].end = id;
		}
		void fail()
		{
			queue<int> q;
			t[root].fail = root;
			for(int i = 0; i < 26; i++)
				if(t[root].to[i])
					q.push(t[root].to[i]),
					t[t[root].to[i]].fail = root;
			while(!q.empty())
			{
				int x = q.front();
				q.pop();
				for(int i = 0; i < 26; i++)
					if(t[x].to[i])
					{
						t[t[x].to[i]].fail = t[t[x].fail].to[i];
						in[t[t[x].to[i]].fail]++;
						q.push(t[x].to[i]);
					}
					else t[x].to[i] = t[t[x].fail].to[i];
			}
		}
		void query(string s)
		{
			int len = s.size();
			int p = root;
			for(int i = 0; i < len; i++)
			{
//				cout << p << " " << t[p].to[s[i]-'a'] << endl;
				if(t[p].to[s[i]-'a']) p = t[p].to[s[i]-'a'];
				else p = t[p].fail;
				t[p].ans++;
			}
		}
		void topo()
		{
			queue<int> q;
			for(int i = 1; i <= cnt; i++)
				if(in[i] == 0)
					q.push(i);
			while(!q.empty())
			{
				int x = q.front();
				q.pop();
				if(t[x].end) Ans[t[x].end] = t[x].ans;
				in[t[x].fail]--; t[t[x].fail].ans += t[x].ans;
				if(in[t[x].fail] == 0) q.push(t[x].fail);
			}
		}
}T;

map<string,int> b,mp;

int main()
{
//	freopen("1.in","r",stdin);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i];
		if(b[s[i]]) continue;
		b[s[i]] = i;
		T.add(s[i],i);
	}
	T.fail();
	cin >> c;
	T.query(c);
	T.topo();
	for(int i = 1; i <= n; i++)
		cout << Ans[b[s[i]]] << endl;
	return 0;
}