http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D

SuffixArray.cpp

#include "bits/stdc++.h"
using namespace std;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 2e9;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

class SuffixArray {
private:
    string s;
    int n;
    vector<int> rank;
    vector<int> sa;
public:
    SuffixArray(string _s) : s(_s) {
        n = s.size();
        rank.resize(n + 1);
        sa.resize(n + 1);
        construct();
    }
    void construct() {
        for (int i = 0; i <= n; ++i) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }

        int k;
        auto compare = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            else {
                int ri = i + k <= n ? rank[i + k] : -1;
                int rj = j + k <= n ? rank[j + k] : -1;
                return ri < rj;
            }
        };

        vector<int> tmp(n + 1);
        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), compare);

            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; ++i) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; ++i) {
                rank[i] = tmp[i];
            }
        }
    }
    bool contain(string t) {
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (s.substr(sa[m], t.size()) < t) l = m;
            else r = m;
        }
        return s.substr(sa[r], t.size()) == t;
    }
    void print() {
        for (int i = 0; i < n; ++i) {
            cerr << s.substr(sa[i]) << endl;
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    string s;
    cin >> s;
    SuffixArray suf(s);
    // suf.print();
    int q;
    cin >> q;
    rep(i, q) {
        string t;
        cin >> t;
        cout << suf.contain(t) << endl;
    }
}