Language: C++


#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;

constexpr ll MOD = 1000000007LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;




class SuffixArray
{
private:
    // static constexpr int encode(const int c) { return c == '$' ? 0 : c - 'a' + 1; }
    // static constexpr char decode(const int n) { return (n == 0 ? '$' : 'a' + n - 1); }
    static constexpr int encode(const int c) { return c == '$' ? 0 : c <= '9' ? 1 + c - '0' : c <= 'Z' ? 11 + c - 'A' : 37 + c - 'a'; }
    static constexpr char decode(const int n) { return n == 0 ? '$' : n <= 10 ? '0' + n - 1 : n <= 36 ? 'A' + n - 11 : 'a' * n - 37; }
    enum class Type : char
    {
        L = 0,
        S = 1,
        LMS = 2,
    };

public:
    SuffixArray(const string& s, const int kind_) : N(s.size() + 1), kind{kind_ + 1}, S(s.size() + 1, 0), type(N), next(N, 1), bucket(kind), num(kind, 0), head(kind, 0), tail(kind, 0)
    {
        for (int i = 0; i < s.size(); i++) {
            S[i] = encode(s[i]);
        }
        initializeData();
        sortLMS();
    }
    SuffixArray(const vector<int>& s, const int kind_) : N(s.size() + 1), kind{kind_ + 1}, S(s), type(N), next(N, 1), bucket(kind), num(kind, 0), head(kind, 0), tail(kind, 0)
    {
        S.push_back(0);
        initializeData();
        sortLMS();
    }
    void debugPrint() const
    {
        for (int i = 0; i < N; i++) {
            cout << decode(S[i]);
        }
        cout << endl;
        for (int i = 0; i < N; i++) {
            cout << (type[i] == Type::L ? "L" : "S");
        }
        cout << endl;
        for (int i = 0; i < N; i++) {
            cout << (type[i] == Type::LMS ? "@" : " ");
        }
        cout << endl;
        for (int i = 0; i < kind; i++) {
            if (bucket[i].empty()) continue;
            cout << "[" << decode(i) << "]:\n";
            for (const int p : bucket[i]) {
                cout << "  " << p << endl;
            }
        }
    }

    vector<int> getSuffixArray() const
    {
        vector<int> ans(N - 1);
        for (int pos = 0, i = 1; i < kind; i++) {  // 番兵以外
            for (const int p : bucket[i]) {
                ans[pos++] = p;
            }
        }
        return ans;
    }

private:
    void initializeData()
    {
        for (const int i : S) {
            num[i]++;
        }
        for (int i = 0; i < kind; i++) {
            bucket[i].resize(num[i], -1);
            tail[i] = num[i] - 1;
        }
        type[N - 1] = Type::S;
        for (int i = N - 2; i >= 0; i--) {
            type[i] = (S[i] != S[i + 1] ? (S[i] < S[i + 1] ? Type::S : Type::L) : type[i + 1]);
            if (type[i] == Type::L and type[i + 1] == Type::S) {
                type[i + 1] = Type::LMS;
                LMS.push_back(i + 1);
            }
        }
        for (int pos = N - 1, i = N - 2; i >= 0; i--) {
            next[i] = pos;
            if (type[i] == Type::LMS) {
                pos = i;
            }
        }
    }

    void sortLMS()
    {
        for (const int l : LMS) {
            insertTail(l);
        }
        induce();
        vector<int> lms;
        for (int i = 0; i < kind; i++) {
            for (const int p : bucket[i]) {
                if (type[p] == Type::LMS) {
                    lms.push_back(p);
                }
            }
        }
        const int size = lms.size();
        vector<int> order(N / 2 + 1, 0);
        int number = 1;
        order[N / 2] = 1;
        bool same = false;
        for (int i = 1; i < size; i++) {
            const int l1 = lms[i - 1];
            const int r1 = next[l1];
            const int l2 = lms[i];
            const int r2 = next[l2];
            if (r1 - l1 == r2 - l2 and vector<int>(S.begin() + l1, S.begin() + r1 + 1) == vector<int>(S.begin() + l2, S.begin() + r2 + 1)) {
                same = true;
            } else {
                number++;
            }
            order[l2 / 2] = number;
        }
        if (same) {
            vector<int> s(size);
            for (int p = 0, i = 0; i <= N / 2; i++) {
                if (order[i] > 0) {
                    s[p++] = order[i];
                }
            }
            const vector<int> sorted = SuffixArray{s, number}.getSuffixArray();
            for (int i = 0; i < kind; i++) {
                head[i] = 0;
                tail[i] = num[i] - 1;
            }
            for (int i = size - 1; i >= 0; i--) {
                insertTail(LMS[size - 1 - sorted[i]]);
            }
            induce();
        } else {
            for (int i = 0; i < kind; i++) {
                head[i] = 0;
                tail[i] = num[i] - 1;
            }
            for (int i = size - 1; i >= 0; i--) {
                insertTail(lms[i]);
            }
            induce();
        }
    }

    void induce()
    {
        for (int i = 0; i < kind; i++) {
            for (int j = 0; j < head[i]; j++) {
                const int p = bucket[i][j];
                if (p > 0 and type[p - 1] == Type::L) {
                    insertHead(p - 1);
                }
            }
            for (int j = tail[i] + 1; j < num[i]; j++) {
                const int p = bucket[i][j];
                if (p > 0 and type[p - 1] == Type::L) {
                    insertHead(p - 1);
                }
            }
        }
        for (int i = 1; i < kind; i++) {  // 番兵以外
            tail[i] = num[i] - 1;
        }
        for (int i = kind - 1; i >= 0; i--) {
            for (int j = num[i] - 1; j > tail[i]; j--) {
                const int p = bucket[i][j];
                if (p > 0 and type[p - 1] != Type::L) {
                    insertTail(p - 1);
                }
            }
            for (int j = head[i] - 1; j >= 0; j--) {
                const int p = bucket[i][j];
                if (p > 0 and type[p - 1] != Type::L) {
                    insertTail(p - 1);
                }
            }
        }
    }
    void insertHead(const int i) { bucket[S[i]][head[S[i]]++] = i; }
    void insertTail(const int i) { bucket[S[i]][tail[S[i]]--] = i; }

    const int N;
    const int kind;
    vector<int> S;               // O(N)
    vector<Type> type;           // O(N)
    vector<int> next;            // O(N)
    vector<vector<int>> bucket;  // O(N)
    vector<int> num;             // O(K)
    vector<int> head;            // O(K)
    vector<int> tail;            // O(K)
    vector<int> LMS;             // O(N)
};



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

int main()
{
    string S;
    cin >> S;
    const auto sa = SuffixArray{S, 62}.getSuffixArray();
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        string P;
        cin >> P;
        cout << (match(S, P, sa) ? 1 : 0) << endl;
    }
}



Compiler output:
a.cc: In function 'int main()':
a.cc:231:18: error: 'match' was not declared in this scope; did you mean 'rpmatch'?
  231 |         cout << (match(S, P, sa) ? 1 : 0) << endl;
      |                  ^~~~~
      |                  rpmatch