Language: C++

#include <string>
#include <vector>
#include <algorithm>

// ------ Suffix Array ------ //
class SuffixArray {
	void CreateBeginBucket(vector<int>&v, vector<int>&bucket) {
		fill(bucket.begin(), bucket.end(), 0);
		for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
		int sum = 0;
		for (int i = 0; i<bucket.size(); i++) { bucket[i] += sum; swap(sum, bucket[i]); }
	}
	void CreateEndBucket(vector<int>&v, vector<int>&bucket) {
		fill(bucket.begin(), bucket.end(), 0);
		for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
		for (int i = 1; i<bucket.size(); i++)bucket[i] += bucket[i - 1];
	}
	void InducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
		CreateBeginBucket(v, bucket);
		for (int i = 0; i<v.size(); i++)if (SA[i]>0 && isL[SA[i] - 1])SA[bucket[v[SA[i] - 1]]++] = SA[i] - 1;
	}
	void InvertInducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
		CreateEndBucket(v, bucket);
		for (int i = v.size() - 1; i >= 0; i--)if (SA[i]>0 && !isL[SA[i] - 1])SA[--bucket[v[SA[i] - 1]]] = SA[i] - 1;
	}
	vector<int>SA_IS(vector<int>v, int mv) {
		if (v.size() == 1)return vector<int>(1, 0);
		vector<int>isL(v.size());
		vector<int>bucket(mv + 1);
		vector<int>SA(v.size(), -1);
		auto isLMS = [&](int x)->bool {return x>0 && isL[x - 1] && !isL[x]; };
		isL[v.size() - 1] = 0;
		for (int i = v.size() - 2; i >= 0; i--)isL[i] = v[i]>v[i + 1] || (v[i] == v[i + 1] && isL[i + 1]);
		CreateEndBucket(v, bucket);
		for (int i = 0; i<v.size(); i++)if (isLMS(i))SA[--bucket[v[i]]] = i;
		InducedSort(v, SA, mv, bucket, isL);
		InvertInducedSort(v, SA, mv, bucket, isL);
		int cur = 0;
		vector<int>ord(v.size());
		for (int i = 0; i<v.size(); i++)if (isLMS(i))ord[i] = cur++;
		vector<int>nxv(cur);
		cur = -1;
		int prev = -1;
		for (int i = 0; i<v.size(); i++) {
			if (!isLMS(SA[i]))continue;
			bool diff = false;
			for (int d = 0; d<v.size(); d++) {
				if (prev == -1 || v[SA[i] + d] != v[prev + d] || isL[SA[i] + d] != isL[prev + d]) {
					diff = true;
					break;
				}
				else if (d>0 && isLMS(SA[i] + d))break;
			}
			if (diff) { cur++; prev = SA[i]; }
			nxv[ord[SA[i]]] = cur;
		}
		vector<int>reord(nxv.size());
		for (int i = 0; i<v.size(); i++)if (isLMS(i))reord[ord[i]] = i;
		vector<int>nxSA = SA_IS(nxv, cur);
		CreateEndBucket(v, bucket);
		for (int i = 0; i<SA.size(); i++)SA[i] = -1;
		for (int i = nxSA.size() - 1; i >= 0; i--)SA[--bucket[v[reord[nxSA[i]]]]] = reord[nxSA[i]];
		InducedSort(v, SA, mv, bucket, isL);
		InvertInducedSort(v, SA, mv, bucket, isL);
		return SA;
	}
	vector<int>SA_IS(string s) {
		vector<int>v(s.size() + 1);
		for (int i = 0; i<s.size(); i++)v[i] = s[i] + 1;
		return SA_IS(v, *max_element(v.begin(), v.end()));
	}
	vector<int>construct_lcp(string &s, vector<int>&sa) {
		vector<int> lcp, rank(s.size() + 1);
		int n = s.size();
		for (int i = 0; i <= n; i++)rank[sa[i]] = i;
		int h = 0;
		lcp[0] = 0;
		for (int i = 0; i<n; i++) {
			int j = sa[rank[i] - 1];
			if (h>0) h--;
			for (; j + h<n&&i + h<n; h++) {
				if (s[j + h] != s[i + h])break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
public:
	string s;
	vector<int> sa, lcp;
	void init(string &T) {
		s = T;
		sa = SA_IS(s);
	}
	SuffixArray(string &t) { init(t); }
	SuffixArray() {}
	bool contain(string &t) {
		int a = 0, b = s.size();
		while (b - a>1) {
			int c = (a + b) / 2;
			if (s.compare(sa[c], t.size(), t) < 0)a = c;
			else b = c;
		}
		return s.compare(sa[b], t.size(), t) == 0;
	}
};

// ------ Main ------ //
int q; string s, t;
int main() {
	cin >> s >> q;
	SuffixArray v(s);
	for(int i = 0; i < q; i++) {
		cin >> t;
		cout << (v.contain(t) ? 1 : 0) << endl;
	}
}

Compiler output:
a.cc:7:32: error: 'vector' has not been declared
    7 |         void CreateBeginBucket(vector<int>&v, vector<int>&bucket) {
      |                                ^~~~~~
a.cc:7:38: error: expected ',' or '...' before '<' token
    7 |         void CreateBeginBucket(vector<int>&v, vector<int>&bucket) {
      |                                      ^
a.cc:13:30: error: 'vector' has not been declared
   13 |         void CreateEndBucket(vector<int>&v, vector<int>&bucket) {
      |                              ^~~~~~
a.cc:13:36: error: expected ',' or '...' before '<' token
   13 |         void CreateEndBucket(vector<int>&v, vector<int>&bucket) {
      |                                    ^
a.cc:18:26: error: 'vector' has not been declared
   18 |         void InducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
      |                          ^~~~~~
a.cc:18:32: error: expected ',' or '...' before '<' token
   18 |         void InducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
      |                                ^
a.cc:22:32: error: 'vector' has not been declared
   22 |         void InvertInducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
      |                                ^~~~~~
a.cc:22:38: error: expected ',' or '...' before '<' token
   22 |         void InvertInducedSort(vector<int>&v, vector<int>&SA, int mv, vector<int>&bucket, vector<int>&isL) {
      |                                      ^
a.cc:26:9: error: 'vector' does not name a type
   26 |         vector<int>SA_IS(vector<int>v, int mv) {
      |         ^~~~~~
a.cc:67:9: error: 'vector' does not name a type
   67 |         vector<int>SA_IS(string s) {
      |         ^~~~~~
a.cc:72:9: error: 'vector' does not name a type
   72 |         vector<int>construct_lcp(string &s, vector<int>&sa) {
      |         ^~~~~~
a.cc:89:9: error: 'string' does not name a type; did you mean 'stdin'?
   89 |         string s;
      |         ^~~~~~
      |         stdin
a.cc:90:9: error: 'vector' does not name a type
   90 |         vector<int> sa, lcp;
      |         ^~~~~~
a.cc:91:19: error: 'string' has not been declared
   91 |         void init(string &T) {
      |                   ^~~~~~
a.cc:95:27: error: expected ')' before '&' token
   95 |         SuffixArray(string &t) { init(t); }
      |                    ~      ^~
      |                           )
a.cc:97:22: error: 'string' has not been declared
   97 |         bool contain(string &t) {
      |                      ^~~~~~
a.cc: In member function 'void SuffixArray::CreateBeginBucket(int)':
a.cc:8:22: error: 'bucket' was not declared in this scope
    8 |                 fill(bucket.begin(), bucket.end(), 0);
      |                      ^~~~~~
a.cc:8:17: error: 'fill' was not declared in this scope; did you mean 'std::fill'?
    8 |                 fill(bucket.begin(), bucket.end(), 0);
      |                 ^~~~
      |                 std::fill
In file included from /usr/include/c++/14/algorithm:86,
                 from a.cc:3:
/usr/include/c++/14/pstl/glue_algorithm_defs.h:191:1: note: 'std::fill' declared here
  191 | fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
a.cc:9:35: error: 'v' was not declared in this scope
    9 |                 for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
      |                                   ^
a.cc:11:75: error: 'swap' was not declared in this scope
   11 |                 for (int i = 0; i<bucket.size(); i++) { bucket[i] += sum; swap(sum, bucket[i]); }
      |                                                                           ^~~~
a.cc:11:75: note: suggested alternatives:
In file included from /usr/include/c++/14/vector:66,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_vector.h:2122:5: note:   'std::swap'
 2122 |     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
      |     ^~~~
In file included from /usr/include/c++/14/bits/new_allocator.h:36,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 from a.cc:1:
/usr/include/c++/14/bits/move.h:226:5: note:   'std::swap'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/move.h:226:5: note:   'std::swap'
a.cc: In member function 'void SuffixArray::CreateEndBucket(int)':
a.cc:14:22: error: 'bucket' was not declared in this scope
   14 |                 fill(bucket.begin(), bucket.end(), 0);
      |                      ^~~~~~
a.cc:14:17: error: 'fill' was not declared in this scope; did you mean 'std::fill'?
   14 |                 fill(bucket.begin(), bucket.end(), 0);
      |                 ^~~~
      |                 std::fill
/usr/include/c++/14/pstl/glue_algorithm_defs.h:191:1: note: 'std::fill' declared here
  191 | fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
a.cc:15:35: error: 'v' was not declared in this scope
   15 |                 for (int i = 0; i<v.size(); i++)bucket[v[i]]++;
      |                                   ^
a.cc: In member function 'void SuffixArray::InducedSort(int)':
a.cc:19:35: error: 'v' was not declared in this scope
   19 |                 CreateBeginBucket(v, bucket);
      |                                   ^
a.cc:19:38: error: 'bucket' was not declared in this scope
   19 |                 CreateBeginBucket(v, bucket);
      |                                      ^~~~~~
a.cc:20:53: error: 'SA' was not declared in this scope
   20 |                 for (int i = 0; i<v.size(); i++)if (SA[i]>0 && isL[SA[i] - 1])SA[bucket[v[SA[i] - 1]]++] = SA[i] - 1;
      |                                                     ^~
a.cc:20:64: error: 'isL' was not declared in this scope
   20 |                 for (int i = 0; i<v.size(); i++)if (SA[i]>0 && isL[SA[i] - 1])SA[bucket[v[SA[i] - 1]]++] = SA[i] - 1;
      |                                                                ^~~
a.cc: In member function 'void SuffixArray::InvertInducedSort(int)':
a.cc:23:33: error: 'v' was not declared in this scope
   23 |                 CreateEndBucket(v, bucket);
      |                                 ^
a.cc:23:36: error: 'bucket' was not declared in this scope
   23 |                 CreateEndBucket(v, bucket);
      |                                    ^~~~~~
a.cc:24:60: error: 'SA' was not declared in this scope
   24 |                 for (int i = v.size() - 1; i >= 0; i--)if (SA[i]>0 && !isL[SA[i] - 1])SA[--bucket[v[SA[i] - 1]]] = SA[i] - 1;
      |                                                            ^~
a.cc:24:72: error: 'isL' was not declared in this scope
   24 |                 for (int i = v.size() - 1; i >= 0; i--)if (SA[i]>0 && !isL[SA[i] - 1])SA[--bucket[v[SA[i] - 1]]] = SA[i] - 1;
      |                                                                        ^~~
a.cc: In member function 'void SuffixArray::init(int&)':
a.cc:92:17: error: 's' was not declared in this scope
   92 |                 s = T;
      |                 ^
a.cc:93:17: error: 'sa' was not declared in this scope
   93 |                 sa = SA_IS(s);
      |                 ^~
a.cc:93:22: error: 'SA_IS' was not declared in this scope
   93 |                 sa = SA_IS(s);
      |                      ^~~~~
a.cc: In member function 'bool SuffixArray::contain(int&)':
a.cc:98:32: error: 's' was not declared in this scope
   98 |                 int a = 0, b = s.size();
      |                                ^
a.cc:101:39: error: 'sa' was not declared in this scope; did you mean 'a'?
  101 |                         if (s.compare(sa[c], t.size(), t) < 0)a = c;
      |                                       ^~
      |                                       a
a.cc:101:48: error: request for member 'size' in 't', which is of non-class type 'int'
  101 |                         if (s.compare(sa[c], t.size(), t) < 0)a = c;
      |                                                ^~~~
a.cc:104:34: error: 'sa' was not declared in this scope; did you mean 'a'?
  104 |                 return s.compare(sa[b], t.size(), t) == 0;
      |                                  ^~
      |                                  a
a.cc:104:43: error: request for member 'size' in 't', which is of non-class type 'int'
  104 |                 return s.compare(sa[b], t.size(), t) == 0;
      |                                           ^~~~
a.cc: At global scope:
a.cc:109:8: error: 'string' does not name a type; did you mean 'stdin'?
  109 | int q; string s, t;
      |        ^~~~~~
      |        stdin
a.cc: In function 'int main()':
a.cc:111:9: error: 'cin' was not declared in this scope
  111 |         cin >> s >> q;
      |         ^~~
a.cc:111:16: error: 's' was not declared in this scope
  111 |         cin >> s >> q;
      |                ^
a.cc:114:24: error: 't' was not declared in this scope
  114 |                 cin >> t;
      |                        ^
a.cc:115:17: error: 'cout' was not declared in this scope
  115 |                 cout << (v.contain(t) ? 1 : 0) << endl;
      |                 ^~~~
a.cc:115:51: error: 'endl' was not declared in this scope
  115 |                 cout << (v.contain(t) ? 1 : 0) << endl;
      |                                                   ^~~~