Language: C++

#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



class suffix_array{
private:
    typedef unsigned long ul;
    
    struct node{
        ll begin;
        ll Rank;
        node* next; //sortで狂ってる
        
        bool operator < (const node &N) const {
            if(Rank==N.Rank){
                return (next==NULL?-1:next->Rank)<(N.next==NULL?-1:N.next->Rank);
            }
            return Rank<N.Rank;
        }
        
        node(ll begin=0,ll Rank=0,node* next=NULL):begin(begin),Rank(Rank),next(next){}
    };
    
    static bool pointer_cmp(const node* &a,const node* &b){return (*a)<(*b);}
    
    vector<node*> sa;
    vector<ll> Rank;
    const string s;
    
    void build(){
        for(int i=0;i<s.size();i++){
            *sa[i]={i,s[i],sa[i+1]};
        }
        sa[s.size()]->begin=s.size();
        sa[s.size()]->Rank=-1;
        sa[s.size()]->next=NULL;
        vector<node*> Next(s.size()+1);
        for(ll k=1;k<=s.size();k<<=1){
            sort(sa.begin(),sa.end(),pointer_cmp);
            Rank[sa[0]->begin]=0;
            Next[0]=(sa[0]->next==NULL?NULL:sa[0]->next->next);
            for(int i=1;i<=s.size();i++){
                Rank[sa[i]->begin]=Rank[sa[i-1]->begin]+(*sa[i-1]<*sa[i]?1:0);
                Next[i]=(sa[i]->next==NULL?NULL:sa[i]->next->next);
            }
            for(int i=0;i<=s.size();i++){
                sa[i]->Rank=Rank[sa[i]->begin];
                sa[i]->next=Next[i];
            }
        }
        for(int i=0;i<=s.size();i++){
            Next[sa[i]->begin]=sa[i];
        }
        for(int i=0;i<=s.size();i++){
            sa[i]->next=sa[i]->begin==s.size()?NULL:Next[sa[i]->begin+1];
        }
    }
    
    //1::greater 0::same -1::less
    int compare(const ul &saf,const string &str){
        for(int i=0;i<str.size();i++){
            if(sa[saf]->begin+i>=s.size()){return -1;}
            if(s[sa[saf]->begin+i]!=str[i]){return s[sa[saf]->begin+i]<str[i]?-1:1;}
        }
        return 0;
    }
    
public:
    suffix_array(const string &str):s(str),Rank(str.size()+1),sa(str.size()+1){
        for(int i=0;i<=str.size();i++){
            
        }
        build();
    }
    
    ll rank(const ul &where) const {return Rank[where];}
    
    ul size() const {return sa.size();}
    
    const node & operator [] (const ul &where) const {return *sa[where];}
    
    //返すのはsuffixの番号
    ul lower_bound(const string &sub){
        ll l=0;
        ll r=s.size();
        while(r-l>4){
            ll m=l+(r-l)/2;
            if(compare(m,sub)==-1){l=m+1;}
            else{r=m;}
        }
        for(ll i=l;i<=r;i++){
            if(compare(i,sub)>=0){return i;}
        }
        return r+1;
    }
    
    //返すのはsuffixの番号
    ul upper_bound(const string &sub){
        ll l=0;
        ll r=s.size();
        while(r-l>4){
            ll m=l+(r-l)/2;
            if(compare(m,sub)<=0){l=m+1;}
            else{r=m;}
        }
        for(ll i=l;i<=r;i++){
            if(compare(i,sub)>0){return i;}
        }
        return r+1;
    }
    
    bool match(const string &sub){
        ll l=0;
        ll r=s.size();
        while(r-l>4){
            ll m=l+(r-l)/2;
            int st=compare(m,sub);
            if(st==0){return true;}
            else if(st==-1){l=m+1;}
            else{r=m-1;}
        }
        for(ll i=l;i<=r;i++){
            if(compare(i,sub)==0){return true;}
        }
        return false;
    }
};


int main(){
    string t;
    cin>>t;
    suffix_array S(t);
    ll q;
    cin>>q;
    while(q--){
        string p;
        cin>>p;
        cout<<S.match(p)<<endl;
    }
    
    return 0;
}



Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/iomanip:42,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<suffix_array::node**, std::vector<suffix_array::node*> >; _Iterator2 = __gnu_cxx::__normal_iterator<suffix_array::node**, std::vector<suffix_array::node*> >; _Compare = bool (*)(const suffix_array::node*&, const suffix_array::node*&)]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = bool (*)(const suffix_array::node*&, const suffix_array::node*&)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:70:17:   required from here
   70 |             sort(sa.begin(),sa.end(),pointer_cmp);
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:30: error: binding reference of type 'const suffix_array::node*&' to 'suffix_array::node*' discards qualifiers
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = suffix_array::node*; _Iterator = __gnu_cxx::__normal_iterator<suffix_array::node**, std::vector<suffix_array::node*> >; _Compare = bool (*)(const suffix_array::node*&, const suffix_array::node*&)]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = bool (*)(const suffix_array::node*&, const suffix_array::node*&)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:70:17:   required from here
   70 |             sort(sa.begin(),sa.end(),pointer_cmp);
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:240:30: error: binding reference of type 'const suffix_array::node*&' to 'suffix_array::node*' discards qualifiers
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<suffix_array::node**, std::vector<suffix_array::node*> >; _Value = suffix_array::node*; _Compare = bool (*)(const suffix_array::node*&, const suffix_array::node*&)]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Distance = long int; _Tp = suffix_array::node*; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Distance = long int; _Tp = suffix_array::node*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<suffix_array::node**, vector<suffix_array::node*> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(const suffix_array::node*&, const suffix_array::node*&)>]'
 1884 |               std::_