Substring searching o(|substring|)

#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

string str;

struct SuffixLink{
    int start;
    int end;
    int to;
    public:
    SuffixLink(){
        to = -1;
    }
    SuffixLink(int s , int e , int t){
        start = s;
        end = e;
        to = t;
    }
};

struct Node{
    int suffix;
    vector<SuffixLink> links;
    public:
    Node(){
        suffix = -1;
        links = vector<SuffixLink>(256 , SuffixLink());
    }
};

vector<Node> tree;
int root , temp;

inline int newNode(){
    tree.pb(Node());
    return sz(tree) - 1;
}

inline int t(int e){
    return (e < 0 ? -e - 1 : str[e]);
}

inline void link(int from , int start , int end , int to){
    tree[from].links[t(start)] = SuffixLink(start , end , to);
}

inline int &f(int v){
    return tree[v].suffix;
}

void initTree(){
    tree.clear();
    temp = newNode();
    root = newNode();

    f(root) = temp;
    rep(i , 256){
        link(temp , -i - 1 , -i , root);
    }
}

pii canonize(int v , int start , int end){
    if(start >= end){
        return {v , start};
    }
    SuffixLink cur = tree[v].links[t(start)];
    while(end - start >= cur.end - cur.start){
        start += cur.end - cur.start;
        v = cur.to;
        if(end > start){
            cur = tree[v].links[t(start)];
        }
    }
    return {v , start};
}

pii testAndSplit(int v , int start , int end , char ch){
    if(start >= end){
        return {tree[v].links[ch].to != -1 , v};
    }
    SuffixLink cur = tree[v].links[t(start)];
    if(ch == t(cur.start + end - start)){
        return {1 , v};
    }
    int md = newNode();
    link(v , cur.start , cur.start + end - start , md);
    link(md , cur.start + end - start , cur.end , cur.to);
    return {0 , md};
}

pii update(int v , int start , int end){
    SuffixLink cur = tree[v].links[t(start)];
    pii splitRes = testAndSplit(v , start , end , t(end));
    int old = root;
    while(splitRes.fi == 0){
        link(splitRes.se , end , INF , newNode());
        if(old != root){
            f(old) = splitRes.se;
        }
        old = splitRes.se;
        pii nwP = canonize(f(v) , start , end);
        v = nwP.fi;
        start = nwP.se;
        splitRes = testAndSplit(v , start , end , t(end));
    }
    if(root != old){
        f(old) = splitRes.se;
    }
    return {v , start};
}

inline void Ukkonen(){
    initTree();
    pii act = {root , 0};
    rep(i , sz(str)){
        act = update(act.fi , act.se , i);
        act = canonize(act.fi , act.se , i + 1);
    }
}

inline bool IsSubstring(string s){
    int v = root;
    int start = 0;
    int end = 0;
    rep(i , sz(s)){
        char cur = s[i];
        if(end == start){
            if(tree[v].links[cur].to == -1){
                return 0;
            }
            start = tree[v].links[cur].start;
            end = start + 1;
        }else{
            if(cur != t(end)){
                return 0;
            }
            ++end;
        }
        if(end == tree[v].links[t(start)].end){
            v = tree[v].links[t(start)].to;
            start = 0;
            end = 0;
        }
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    cin >> str;
    Ukkonen();
    string test;
    while(cin >> test){
        if(IsSubstring(test)){
            die("YES");
        }else{
            die("NO");
        }
    }
    return 0;
}