求条玄关

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
using ll = long long;
using PII = pair<int, int>;

const int MAXN = 2e5 + 5;

int id = 1;

struct tr{
    int son[26], flag, fail, r, tag, vis;
    tr() {
        memset(son, 0, sizeof son);
        flag = fail = r = tag = 0, vis = 0;
    }
} trie[MAXN];
unordered_map<int, int> mp;

void trieADD(const string &s, const int &UID) {
    int pos = 1;
    for(int i = 0; i < (int)s.size(); i ++) {
        if(trie[pos].son[s[i] - 'a'] == 0) {
            trie[pos].son[s[i] - 'a'] = ++id, pos = id;
        } else {
            pos = trie[pos].son[s[i] - 'a'];
        }
        if(i + 1 == (int)s.size()) trie[pos].flag = UID; mp[UID] = trie[pos].flag;
    }
}

void getFAIL() {
    queue<int> que;
    for(int i = 0; i < 26; i ++) trie[0].son[i] = 1;
    trie[1].fail = 0, que.push(1);
    while(que.size()) {
        int u = que.front(); que.pop();
        int uFAIL = trie[u].fail;
        for(int i = 0; i < 26; i ++) {
            if(trie[u].son[i] == 0) {
                trie[u].son[i] = trie[uFAIL].son[i]; 
                continue;
            } //cerr << uFAIL << " " << trie[uFAIL].son[i] << " " << "\n";
            trie[trie[u].son[i]].fail = trie[uFAIL].son[i], que.push(trie[u].son[i]);
            trie[trie[trie[u].son[i]].fail].r ++;
        }
    }
}

unordered_map<int, int> ans;
unordered_map<int, int> mp1;
unordered_map<string, int> mps;
int maxn = 0;

void CALC(const string &s) {
    
    int u = 1; maxn = 0;
    for(int i = 0; i < (int)s.size(); i ++) {
        int tmp = s[i] - 'a';
        u = trie[u].son[tmp];
        trie[u].tag ++;
    }
}
// void CALC(const string &s) {
//     int u = 1;;
//     for(int i = 0; i < (int)s.size(); i ++) {
//         int tmp = s[i] - 'a';
//         int pos = trie[u].son[tmp];
//         while(pos > 1 && trie[pos].flag != -1) {
//             ans += trie[pos].flag, trie[pos].flag = -1;
//             pos = trie[pos].fail;
//         }
//         u = trie[u].son[tmp];
//     }
// }

void topo(){
    queue<int> q;
	for(int i = 1; i <= id; i ++) if(trie[i].r == 0) q.push(i);
	while(!q.empty()){
		int u = q.front(); q.pop();
        trie[trie[u].flag].vis = trie[u].tag;
		int v = trie[u].fail; 
        trie[v].r --, trie[v].tag += trie[u].tag;
		if(trie[v].r == 0) q.push(v);
	}
}


string im[MAXN];

void solve() {
    maxn = 0;
    int n; cin >> n;
    string s;
    for(int i = 0; i <= n; i ++) trie[i].fail = trie[i].flag = 0, memset(trie[i].son, 0, sizeof trie[i].son);
    for(int i = 1; i <= n; i ++) {
        cin >> im[i], trieADD(im[i], i);
        
    }
    cin >> s;
    getFAIL();
    ans.clear();
    CALC(s); topo();
    for(int i = n; i >= 1; i --) {
        if(mps[im[i]] == 0) mp1[i] = i;
        else mp1[i] = mps[im[i]];
        mps[im[i]] = i;
    }
    for(int i = 1; i <= n; i ++) cout << trie[mp[mp1[i]]].vis << "\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    // freopen("P3808_2.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}