Language: C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>

#define REP(i, n) for (int i=0;i<int(n);++i)
#define REPV(i, v, n) for (int i=0,tmp=v;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)

using namespace std;

typedef unsigned char byte;

byte mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
#define tget(i) !!(t[(i)>>3]&mask[(i)&7])
#define tset(i, b) t[(i)>>3]=(b) ? (mask[(i)&7]|t[(i)>>3]) : ((~mask[(i)&7])&t[(i)>>3])
#define chr(i) (cs==sizeof(int)?((int*)s)[i]:((byte *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))

void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
  fill(bkt, bkt + K + 1, 0);
  REP(i,n)bkt[chr(i)]++;
  REPV(i, 0, K+1)tmp += bkt[i], bkt[i] = end ? tmp : tmp - bkt[i];
}

void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
  getBuckets(s, bkt, n, K, cs, end);
  REP(i,n)if(SA[i]>0 && !tget(SA[i]-1)) SA[ bkt[chr(SA[i]-1)]++ ] = SA[i]-1;
}

void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
  getBuckets(s, bkt, n, K, cs, end);
  DWN(i,n,0)if(SA[i]>0 && tget(SA[i]-1))SA[--bkt[chr(SA[i]-1)]] = SA[i]-1;
}

void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
  byte t[(n >> 3) + 1];
  int bkt[K + 1],n1=0,name=0;

  tset(n-2, 0), tset(n-1, 1);
  DWN(i,n-2,0)tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1))));
  getBuckets(s, bkt, n, K, cs);
  fill(SA, SA+n, -1);
  FOR(i,1,n)if(isLMS(i))SA[--bkt[chr(i)]] = i;

  induceSAl(t, SA, s, bkt, n, K, cs);
  induceSAs(t, SA, s, bkt, n, K, cs);

  REP(i,n)if(isLMS(SA[i]))SA[n1++] = SA[i];
  fill(SA + n1, SA + n, -1);

  REPV(i,-1,n1){
    int pos = SA[i], diff = false;
    for(int d = 0; d < n && !diff; d++){
      diff = chr(pos+d) != chr(tmp+d) || tget(pos+d) != tget(tmp+d);
      if(!diff && d && (isLMS(pos+d) || isLMS(tmp+d)))break;
    }
    if(diff)name++,tmp=pos;
    SA[ n1 + ((pos - (pos & 1)) >> 1) ] = name - 1;
  }
  int *s1 = SA + n - n1;
  for(int i=n-1,j=n-1;i>=n1;i--)if(SA[i]>=0)SA[j--]=SA[i];
  if(name < n1)SA_IS((byte*)s1, SA, n1, name - 1, sizeof(int));
  else REP(i,n1)SA[s1[i]]=i;

  getBuckets(s, bkt, n, K, cs);
  for(int i = 1, j = 0; i < n; i++)if(isLMS(i))s1[j++] = i;
  REP(i,n1)SA[i]=s1[SA[i]];
  fill(SA + n1, SA + n, -1);

  DWN(i,n1,0){
    int tmp = SA[i];
    SA[i] = -1, SA[--bkt[chr(tmp)]] = tmp;
  }
  induceSAl(t, SA, s, bkt, n, K, cs);
  induceSAs(t, SA, s, bkt, n, K, cs);
}

const int maxn = 1000001;
int n,sa[maxn];

bool contain(string S, int *sa, string T){
  int a = 0, b = S.length();
  while( b - a > 1 ){
    int c = (a + b ) / 2;
    if ( S.compare(sa[c], T.length(), T) < 0 ) a = c;
    else b = c;
  }
  return S.compare(sa[b], T.length(), T) == 0;
}

char a[maxn],b[maxn];

int main(void){
  int q;
  scanf("%s", a);
  string s = string(a);
  SA_IS((byte*) s.c_str(), sa, s.size()+1);

  scanf("%d", &q);
  while(q--){
    scanf("%s", b);
    if(contain(s, sa, string(b))) printf("1\n");
    else printf("0\n");
  }

  return 0;
}

Compiler output:
a.cc:16:1: error: reference to 'byte' is ambiguous
   16 | byte mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
      | ^~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:38,
                 from /usr/include/c++/14/string:68,
                 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/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:22:6: error: variable or field 'getBuckets' declared void
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |      ^~~~~~~~~~
a.cc:22:17: error: reference to 'byte' is ambiguous
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                 ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:22:23: error: 's' was not declared in this scope
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                       ^
a.cc:22:26: error: expected primary-expression before 'int'
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                          ^~~
a.cc:22:36: error: expected primary-expression before 'int'
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                    ^~~
a.cc:22:43: error: expected primary-expression before 'int'
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                           ^~~
a.cc:22:50: error: expected primary-expression before 'int'
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                  ^~~
a.cc:22:58: error: expected primary-expression before 'bool'
   22 | void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                          ^~~~
a.cc:28:6: error: variable or field 'induceSAl' declared void
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |      ^~~~~~~~~
a.cc:28:16: error: reference to 'byte' is ambiguous
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:28:22: error: 't' was not declared in this scope; did you mean 'tm'?
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                      ^
      |                      tm
a.cc:28:25: error: expected primary-expression before 'int'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                         ^~~
a.cc:28:34: error: reference to 'byte' is ambiguous
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                  ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:28:40: error: 's' was not declared in this scope
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                        ^
a.cc:28:43: error: expected primary-expression before 'int'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                           ^~~
a.cc:28:53: error: expected primary-expression before 'int'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                                     ^~~
a.cc:28:60: error: expected primary-expression before 'int'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                                            ^~~
a.cc:28:67: error: expected primary-expression before 'int'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                                                   ^~~
a.cc:28:75: error: expected primary-expression before 'bool'
   28 | void induceSAl(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=false){
      |                                                                           ^~~~
a.cc:33:6: error: variable or field 'induceSAs' declared void
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |      ^~~~~~~~~
a.cc:33:16: error: reference to 'byte' is ambiguous
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:33:22: error: 't' was not declared in this scope; did you mean 'tm'?
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                      ^
      |                      tm
a.cc:33:25: error: expected primary-expression before 'int'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                         ^~~
a.cc:33:34: error: reference to 'byte' is ambiguous
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                  ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:33:40: error: 's' was not declared in this scope
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                        ^
a.cc:33:43: error: expected primary-expression before 'int'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                           ^~~
a.cc:33:53: error: expected primary-expression before 'int'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                     ^~~
a.cc:33:60: error: expected primary-expression before 'int'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                            ^~~
a.cc:33:67: error: expected primary-expression before 'int'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                                   ^~~
a.cc:33:75: error: expected primary-expression before 'bool'
   33 | void induceSAs(byte *t, int *SA, byte *s, int *bkt, int n, int K, int cs, bool end=true){
      |                                                                           ^~~~
a.cc:38:6: error: variable or field 'SA_IS' declared void
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |      ^~~~~
a.cc:38:12: error: reference to 'byte' is ambiguous
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |            ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef unsigned char byte;
      |                       ^~~~
a.cc:38:18: error: 's' was not declared in this scope
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |                  ^
a.cc:38:21: error: expected primary-expression before 'int'
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |                     ^~~
a.cc:38:30: error: expected primary-expression before 'int'
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |                              ^~~
a.cc:38:37: error: expected primary-expression before 'int'
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |                                     ^~~
a.cc:38:48: error: expected primary-expression before 'int'
   38 | void SA_IS(byte *s, int *SA, int n, int K=128, int cs=1) {
      |                                                ^~~
a.cc: In function 'int main()':
a.cc:100:10: error: reference to 'byte' is ambiguous
  100 |   SA_IS((byte*) s.c_str(), sa, s.size()+1);
      |          ^~~~
/usr/include/c++/14/cstddef:70:14: note: candidates are: 'enum class std::byte'
   70 |   enum class byte : unsigned char {};
      |              ^~~~
a.cc:14:23: note:                 'typedef unsigned char byte'
   14 | typedef