Light OJ 1427 / Aho-Corasick

/***
 created: 2023-02-21-21.07.56
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll int
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'

/* Template Aho-Corasick by Anachor */

namespace Aho{

const int N = 5e5 + 7;        ///Number of characters in dictionary
const int K = 26;           ///Alphabet size

int nxt[N][K];              ///Children
int go[N][K];               ///automaton

int link[N];                ///Suffix link
bool leaf[N];               ///isLeaf
int par[N];                 ///Parent
char ch[N];                 ///character of incoming edge
int ex[N];                  ///exit link
int sz;
vector<int> finish[N];      ///finish string index

void init()
{
    memset(nxt, -1, sizeof nxt);
    memset(go, -1, sizeof go);
    memset(link, -1, sizeof link);
    memset(leaf, 0, sizeof leaf);
    memset(ex, -1, sizeof ex);
    for (int i = 0; i < N; i++)
    {
        finish[i].clear( );
    }
    sz = 0;
}

void addString(const string &s, int ind)
{
    int cur = 0;
    for (char c: s)
    {
        int cc = c-'a';
        if (nxt[cur][cc] == -1)
        {
            nxt[cur][cc] = ++sz;
            ch[sz] = c;
            par[sz] = cur;
        }
        cur = nxt[cur][cc];
    }
    leaf[cur] = 1;
    finish[cur].emplace_back(ind);
}

int Go(int v, char ch);

///Amortized O(1)
int getlink(int v)
{
    if (link[v] != -1)  return link[v];
    if (v==0 || par[v] == 0)    return link[v] = 0;
    else return link[v] = Go(getlink(par[v]), ch[v]);
}

///Amortized O(1)
int Go (int v, char c)
{
    int cc = c- 'a';
    if (go[v][cc] != -1)     return go[v][cc];
    if (nxt[v][cc] != -1)    return go[v][cc] = nxt[v][cc];
    else return go[v][cc] = (v ? Go(getlink(v), c) : 0);
}

///Amortized O(1)
int exitlink(int v)
{
    if (ex[v] != -1)             return ex[v];
    int nxt = getlink(v);
    if (nxt==0 || leaf[nxt])     return ex[v] = nxt;
    return ex[v] = exitlink(nxt);
}


///returns number of matches (including multiple matches)
///O(no of matches + length of s)
int match(string s)
{
    int cur = 0;
    int ans = 0;
    for (auto c: s)
    {
        cur = Go(cur, c);
        int e = (leaf[cur] ? cur : exitlink(cur));
        while (e)
            ans++,
                e = exitlink(e);
    }
    return ans;
}
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        Aho::init();

        ll n;

        string a,b;

        cin>>n;

        cin>>a;

        vector<ll>ans(n,0);

        for(ll i=0; i<n; i++)
        {
            cin>>b;
            Aho::addString(b,i);
        }

        ll cur=0;

        for(ll i=0; a[i]; i++)
        {
            cur=Aho::Go(cur,a[i]);

            ll en;

            if(Aho::leaf[cur]) en=cur;
            else en=Aho::exitlink(cur);

            while(en>0)
            {
                for (ll j:Aho::finish[en]) ans[j]++;

                en=Aho::exitlink(en);
            }
        }

        cout<<"Case "<<cs<<":"<<nl;

        for(ll i:ans) cout<<i<<nl;
    }
    return 0;
}