aho updated

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1e9 + 7;

const int N = 5e5 + 10;

string s,pat[1001];int n,tot = 1,par[N],depth[N],pl[N],sl[N],to[N][130],arr[N],lev[N];
vector<int> tr[N];int nxt[N][130],ans[N],vis[N];

void Insert(string temp,int indx) {
    int uu = 1;
    for(int i = 0; i < temp.size(); i++) {
        int id = temp[i];
        if(!to[uu][id]) {
            to[uu][id] = ++tot;
            depth[tot] = depth[uu] + 1;
            par[tot] = uu;
            pl[tot] = id;
        }
        uu = to[uu][id];
    }
    lev[indx] = uu;
}

void push_links() {
    queue<int> qu;
    qu.push(1);
    while(!qu.empty()) {
        int vv = qu.front();
        qu.pop();
        if(depth[vv] <= 1) sl[vv] = 1;
        else {
            int uu = sl[par[vv]];
            int l = pl[vv];
            while(uu > 1 && !to[uu][l]) uu = sl[uu];
            if(to[uu][l]) uu = to[uu][l];
            sl[vv] = uu;
        }
        if(vv != 1) tr[sl[vv]].push_back(vv);
        for(int i = 0; i < 130; i++) if(to[vv][i]) qu.push(to[vv][i]);
    }
}

int jump(int curr,int id) {
    if(nxt[curr][id]) return nxt[curr][id];
    int uu = curr;
    while(curr > 1 && !to[curr][id]) curr = sl[curr];
    if(to[curr][id]) curr = to[curr][id];
    return nxt[uu][id] = curr;
}
void dfs(int s) {
    if(vis[s]) return ;
    vis[s] = 1;
    for(auto it : tr[s]) {
        dfs(it);
        arr[s] += arr[it];
    }
}
int main() {

    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    cin >> s;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> pat[i];
        Insert(pat[i],i);
    }
    push_links();
    int curr = 1;
    for(int i = 0; i < s.size(); i++) {
        int id = s[i];
        int x = jump(curr,id);
        curr = x;
        arr[x] ++;
        //cout << x << " " << i << endl;
    }
    for(int i = 1; i <= tot; i++) {
        if(!vis[i]) dfs(i);
    }
    for(int i = 0; i < n; i++) {
        if(arr[lev[i]]) cout << "Y";
        else cout << "N";
        //cout << " " << arr[lev[i]] ;
        cout << "\n";
    }
    return 0;
}