求卡常

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

int h[2 * N], nxt[3 * N], to[3 * N], cnt;

char c[3 * N];

inline void add (const int u, const char v) {
	c[ ++ cnt] = v;
	nxt[cnt] = h[u];
	h[u] = cnt;
	return;
}

int q[2 * N], l, r;

struct Map {
	int id, M;
	inline int& operator [] (const int x) {
		if (M >> x & 1) {
			for (int i = h[id]; i; i = nxt[i] ) {
				if (c[i] == x) return to[i];
			}
		}
		M |= (1 << x);
		add(id, x);
		return to[h[id]];   
	}
	inline bool count (const int x) {   
		return M >> x & 1;
	}
};

struct node {
	int fa, len;
	int siz;
	Map son;
};

struct SAM {
	node t[2 * N];
	
	int d[2 * N];
	
	int lst, idx;
	
	SAM() {
		lst = idx = 1;
	}
	
	inline void insert (const char c) {
		const int now = ++ idx;
		t[now].son.id = idx;
		t[now].len = t[lst].len + 1;
		t[now].siz = 1;
		int p = lst;
		lst = now;
		const int w = c - 'a';
		while (p && !t[p].son[w]) {
			t[p].son[w] = now;
			p = t[p].fa;
		}
		if (!p) {
			t[now].fa = 1;
			return;
		}
		const int q = t[p].son[w];
		if (t[q].len == t[p].len + 1) {
			t[now].fa = q;
			return;
		}
		t[ ++ idx] = t[q];
		t[idx].siz = 0;
		t[idx].son.id = idx;
		for (int i = h[t[q].son.id]; i; i = nxt[i] ) {
			const int v = ::c[i];
			add(idx, v);
			t[idx].son[v] = to[i];
		}
		t[idx].len = t[p].len + 1;
		t[now].fa = t[q].fa = idx;
		while (p && t[p].son[w] == q) {
			t[p].son[w] = idx;
			p = t[p].fa;
		}
		return;
    }
	
	void build() {
		for (int i = 1; i <= idx; ++ i ) ++ d[t[i].fa];
		
		l = 1, r = 0;
		for (int i = 1; i <= idx; ++ i )
		    if (!d[i])
		        q[ ++ r] = i;
		    
		while (l <= r) {
			const int u = q[l];
			++ l;
			if (!t[u].fa) continue;
			t[t[u].fa].siz += t[u].siz;
			-- d[t[u].fa];
			if (!d[t[u].fa]) q[ ++ r] = t[u].fa; 
		}
		return;
	}
	
	inline int query (const string s) {
		int at = 1;
		for (char c : s) {
			if (!t[at].son.count(c - 'a')) return 0;
			at = t[at].son[c - 'a'];
		}
		return t[at].siz;
	}
	
} T;

string t[200005], s;

int n;

signed main() {
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) cin >> t[i];
	
	cin >> s;
	
	for (char c : s) T.insert(c);
	
	T.build();
	
	for (int i = 1; i <= n; ++ i ) cout << T.query(t[i]) << '\n';
	
	return 0;
}