#295355 (C++17) No.430 文字列検索

提出ソース
結果

問題	No.430 文字列検索
コンテスト
ユーザー	xuzijian629
提出日時	2018-10-31 12:54:21
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	11 ms / 2,000 ms
コード長	8,967 bytes
コンパイル時間	2,068 ms
コンパイル使用メモリ	207,872 KB
最終ジャッジ日時	2025-01-06 15:11:49
ジャッジサーバーID （参考情報）	judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 14
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

// template <class T = i64>
// class SegTree {
//     using F = function<T(T, T)>;
//     int n;
//     vector<T> data;
//     const F f;
//     const T e;

// public:
//     SegTree(const vector<T>& as, const F f = [](T a, T b){ return min(a, b); }, const T e = 1e9) : f(f), e(e) {
//         n = 1;
//         while (n < as.size()) n <<= 1;
//         data = vi(2 * n, e);
//         for (int i = 0; i < as.size(); i++) {
//             data[n + 1] = as[i];
//         }
//         for (int i = n - 1; i > 0; i--) {
//             data[i] = f(data[2 * i], data[2 * i] + 1);
//         }
//     }

//     void update(int k, const T& x) {
//         k += n;
//         data[k] = x;
//         while (k >>= 1) {
//             data[k] = f(data[2 * k], data[2 * k] + 1);
//         }
//     }

//     T query(int a, int b) {
//         T L = e, R = e;
//         for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
//             if (a & 1) {
//                 L = f(L, data[a++]);
//             }
//             if (b & 1) {
//                 R = f(data[b--], R);
//             }
//         }
//         return f(L, R);
//     }
    
//     T operator[](const int& k) const {
//         return data[k + n];
//     }
// };

class SuffixArray {
    vi sa_is(const vi& arr, const int k) {
        const int n = arr.size();
        vector<bool> is_S(n);
        is_S[n - 1] = 1;
        vector<bool> is_LMS(n);
        vi LMSs;
        for (int i = n - 2; i >= 0; i--) {
            is_S[i] = arr[i] < arr[i + 1] || (arr[i] == arr[i + 1] && is_S[i + 1]);
        }
        for (int i = 0; i < n; i++) {
            if (is_S[i] && (i == 0 || !is_S[i - 1])) {
                is_LMS[i] = 1;
                LMSs.push_back(i);
            }
        }
        vi pseudo_sa = induced_sort(arr, LMSs, is_S, k);
        vi orderedLMSs(LMSs.size());
        int id = 0;
        for (int x: pseudo_sa) {
            if (is_LMS[x]) {
                orderedLMSs[id++] = x;
            }
        }
        pseudo_sa[orderedLMSs[0]] = 0;
        int rk = 0;
        if (orderedLMSs.size() > 1) {
            pseudo_sa[orderedLMSs[1]] = ++rk;
        }
        for (int i = 1; i < orderedLMSs.size() - 1; i++) {
            bool is_diff = 0;
            for (int j = 0; j < n; j++) {
                int p = orderedLMSs[i] + j;
                int q = orderedLMSs[i + 1] + j;
                if (arr[p] != arr[q] || is_LMS[p] != is_LMS[q]) {
                    is_diff = 1;
                    break;
                }
                if (j > 0 && is_LMS[p]) {
                    break;
                }
            }
            pseudo_sa[orderedLMSs[i + 1]] = is_diff ? ++rk : rk;
        }
        vi new_arr(LMSs.size());
        id = 0;
        for (int i = 0; i < n; i++) {
            if (is_LMS[i]) {
                new_arr[id++] = pseudo_sa[i];
            }
        }
        vi LMS_sa;
        if (rk + 1 == LMSs.size()) {
            LMS_sa = orderedLMSs;
        } else {
            LMS_sa = sa_is(new_arr, rk + 1);
            for (auto& x: LMS_sa) {
                x = LMSs[x];
            }
        }
        return induced_sort(arr, LMS_sa, is_S, k);
    }

    vi induced_sort(const vi& arr, const vi& LMSs, const vector<bool>& is_S, const int k) {
        const int n = arr.size();
        vi buckets(n);
        vi cs(k + 1);
        for (int c: arr) {
            cs[c + 1]++;
        }
        for (int i = 0; i < k; i++) {
            cs[i + 1] += cs[i];
        }
        vi cnt(k);
        for (int i = LMSs.size() - 1; i >= 0; i--) {
            int c = arr[LMSs[i]];
            buckets[cs[c + 1] - 1 - cnt[c]++] = LMSs[i];
        }
        cnt = vi(k);
        for (int i = 0; i < n; i++) {
            if (buckets[i] == 0 || is_S[buckets[i] - 1]) continue;
            int c = arr[buckets[i] - 1];
            buckets[cs[c] + cnt[c]++] = buckets[i] - 1;
        }
        cnt = vi(k);
        for (int i = n - 1; i >= 0; i--) {
            if (buckets[i] == 0 || !is_S[buckets[i] - 1]) continue;
            int c = arr[buckets[i] - 1];
            buckets[cs[c + 1] - 1 - cnt[c]++] = buckets[i] - 1;
        }
        return buckets;
    }

public:
    string S;
    int N;

    vi sa;
    // sa[i]: suffixが辞書順i番目となる開始位置のindex

    SuffixArray(string s) : S(s), N(s.size()) {
        s += '$';
        vi str(N + 1);
        for (int i = 0; i <= N; i++) {
            str[i] = s[i] - '$';
        }
        sa = sa_is(str, 128);
        sa.erase(sa.begin());
    }

    int operator[](int id) {
        return sa[id];
    }

    vi::iterator lower_bound(string s) {
        // sizeがsと等しく初めてs以上になるようなSの部分文字列(sa)
        int l = -1, r = N;
        while (l < r - 1) {
            int m = (l + r) / 2;
            if (S.compare(sa[m], s.size(), s) < 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return sa.begin() + r;
    }
    
    vi::iterator upper_bound(string s) {
        // sizeがsと等しく初めてsより大きくなるようなSの部分文字列(sa)
        int l = -1, r = N;
        while (l < r - 1) {
            int m = (l + r) / 2;
            if (S.compare(sa[m], s.size(), s) <= 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return sa.begin() + r;
    }

    int cntsub(string s) {
        // sが部分文字列として何回出現するか
        return upper_bound(s) - lower_bound(s);
    }
};

// class LongestCommonPrefix {
//     SegTree<> seg;
//     vi lcp, lcp_begin;
//     // lcp[i]: S[sa[i]..]とS[sa[i + 1]..]が先頭何文字一致しているか、lcp[N - 1] = 0
//     // lcp_begin[i]: S[0..]とS[i..]が先頭何文字一致しているか
// public:
//     const string S;
//     int N;
//     vi sa;
//     vi rk;

//     LongestCommonPrefix();
//     LongestCommonPrefix(const string& s) : S(s), N(s.size()), rk(s.size()), lcp(s.size()) {
//         sa = SuffixArray(s).sa;
//         for (int i = 0; i < N; i++) {
//             rk[sa[i]] = i;
//         }
//         int k = 0;
//         for (int i = 0; i < N: i++) {
//             if (k > 0) k--;
//             if (rk[i] == N - 1) continue;
//             for (int j = sa[rk[i] + 1]; i + k < N && j + k < N; k++) {
//                 if (S[i + k] != S[j + k]) break;
//             }
//             lcp[rk[i]] = k;
//         }

        
//     }
    



// };

// class LongestCommonPrefix {
//   SegTree<> rmq;
//   VI lcp; // lcp[i]: S[sa[i]..]とS[sa[i + 1]..]が先頭何文字一致しているか、lcp[N - 1] = 0
//   VI lcp_begin; // lcp_begin[i]: S[0..]とS[i]が先頭何文字一致しているか
// public:
//   const string S; int N;
//   VI sa;
//   VI rank; // rank[i]: iから始まるsuffixの辞書順での順位
//   LongestCommonPrefix();
//   LongestCommonPrefix(const string& str) : S(str), N(str.size()), rank(str.size()), lcp(str.size()) {
//     sa = SuffixArray(str).sa;
//     // rankの設定
//     REP (i, N) { rank[sa[i]] = i; }
//     // S[i]を順番に見ていきS[i - 1] -　1文字以上が共通することを利用してしゃくとり
//     lcp = VI(N);
//     int h = 0;
//     REP (i, N) {
//       if (h > 0) h--;
//       if (rank[i] == N - 1) continue;
//       int j = sa[rank[i] + 1]; // 比べる対象(辞書順が一つ大きいもの)
//       for (; i + h < N && j + h < N; h++) {
//         if (S[i + h] != S[j + h]) break;
//       }
//       lcp[rank[i]] = h;
//     }
//     // 必要に応じてコメントアウト
//     set_query1();
//     // set_quety2();
//   }
//   int operator[](int index) {
//     return lcp[index];
//   }

//   // S[i..], S[j..]が先頭何文字一致しているか
//   int query(int i, int j) {
//     assert(0 <= i && 0 <= j && i < N && j < N);
//     if (i == j) return N - i;
//     int l = min(rank[i], rank[j]);
//     int r = max(rank[i], rank[j]);
//     return rmq.query(l, r);
//   }
//   void set_query2() {
//     // S[i..], S[j..]のlcpが求められるようにRMQ上にのせる
//     rmq = SegTree<int>(lcp, [](int a, int b) { return min(a, b); }, 1e15);
//   }

//   // S[i..]がS[0..]と先頭文字一致しているか
//   int query(int i) {
//     return lcp_begin[i];
//   }
//   void set_query1() {
//     lcp_begin = VI(N); lcp_begin[0] = N;
//     for (int i = rank[0] - 1; i >= 0; i--) {
//       lcp_begin[sa[i]] = min(lcp_begin[sa[i + 1]], lcp[i]);
//     }
//     for (int i = rank[0] + 1; i < N; i++) {
//       lcp_begin[sa[i]] = min(lcp_begin[sa[i - 1]], lcp[i - 1]);
//     }
//   }
// };


int main() {
    i64 cnt = 0;
    string s;
    cin >> s;
    SuffixArray sa(s);
    int m;
    cin >> m;
    while (m--) {
        string t;
        cin >> t;
        cnt += sa.cntsub(t);
    }
    cout << cnt << endl;
}
yukicoder

結果

ソースコード
