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

提出ソース
結果

問題	No.430 文字列検索
ユーザー	minato
提出日時	2021-01-25 05:11:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	10 ms / 2,000 ms
コード長	11,934 bytes
コンパイル時間	3,031 ms
コンパイル使用メモリ	226,820 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-10 00:53:01
合計ジャッジ時間	3,137 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	9 ms 5,248 KB
testcase_02	AC	6 ms 5,248 KB
testcase_03	AC	6 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	6 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	10 ms 5,248 KB
testcase_12	AC	10 ms 5,248 KB
testcase_13	AC	10 ms 5,248 KB
testcase_14	AC	9 ms 5,248 KB
testcase_15	AC	8 ms 5,248 KB
testcase_16	AC	5 ms 5,248 KB
testcase_17	AC	5 ms 5,248 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vector<T>>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
constexpr char ln = '\n';
istream& operator>>(istream& is, __int128_t& x) {
    x = 0;
    string s;
    is >> s;
    int n = int(s.size()), it = 0;
    if (s[0] == '-') it++;
    for (; it < n; it++) x = (x * 10 + s[it] - '0');
    if (s[0] == '-') x = -x;
    return is;
}
ostream& operator<<(ostream& os, __int128_t x) {
    if (x == 0) return os << 0;
    if (x < 0) os << '-', x = -x;
    deque<int> deq;
    while (x) deq.emplace_front(x % 10), x /= 10;
    for (int e : deq) os << e;
    return os;
}
template<class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template<class T> 
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (int i = 0; i < int(v.size()); i++) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "}";
}
template<class Container> inline int SZ(const Container& v) { return int(v.size()); }
template<class T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }
template<class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; }
template<class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; }
inline int topbit(ull x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(ull x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(ull x) { return __builtin_popcountll(x); }
inline int kthbit(ull x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x-1) * 10; }
template<class T> inline T ABS(T x) { return max(x, -x); }
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
inline void YES(bool t = 1) { cout << YESNO[t] << "\n"; }
inline void Yes(bool t = 1) { cout << YesNo[t] << "\n"; }
inline void yes(bool t = 1) { cout << yesno[t] << "\n"; }
inline void print() { cout << "\n"; }
template<class T>
inline void print(const vector<T>& v) {
    for (auto it = begin(v); it != end(v); ++it) {
        if (it != begin(v)) cout << " ";
        cout << *it;
    }
    print();
}
template<class T, class... Args>
inline void print(const T& x, const Args& ... args) {
    cout << x << " ";
    print(args...);
}
#ifdef MINATO_LOCAL
inline void debug_out() { cerr << endl; }
template <class T, class... Args>
inline void debug_out(const T& x, const Args& ... args) {
    cerr << " " << x;
    debug_out(args...);
}
#define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__)
#else
#define debug(...) (void(0))
#endif
struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(7); }; } fast_ios_;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<class T>
struct SuffixArray {
  public:
    SuffixArray() {}
    SuffixArray(const string& s) : n_(int(s.size())), data(s.size()), invs(s.size()) {
        vector<int> s2(n_);
        for (int i = 0; i < n_; i++) {
            data[i] = s2[i] = s[i];
        }

        sa_ = sa_is(s2,255);

        for (int i = 0; i < n_; i++) {
            invs[sa_[i]] = i;
        }
    }
    SuffixArray(const vector<T>& s) : n_(int(s.size())), data(s), invs(s.size()) {
        vector<int> idx(n_);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
        vector<int> s2(n_);
        int now = 0;
        for (int i = 0; i < n_; i++) {
            if (i && s[idx[i - 1]] != s[idx[i]]) now++;
            s2[idx[i]] = now;
        }

        sa_ = sa_is(s2, now);

        for (int i = 0; i < n_; i++) {
            invs[sa_[i]] = i;
        }
    }
    SuffixArray(const vector<int>& s, int upper) : n_(int(s.size())), data(s.size()), invs(s.size()) {
        assert(0 <= upper);
        for (int i = 0; i < n_; i++) {
            assert(0 <= s[i] && s[i] <= upper);
            data[i] = s[i];
        }
        
        auto sa_ = sa_is(s, upper);
        
        for (int i = 0; i < n_; i++) {
            invs[sa_[i]] = i;
        }
    }

    int size() const { return n_; }

    int operator[](int i) const {
        assert(0 <= i and i < n_);
        return sa_[i];
    }

    int inv(int i) const {
        assert(0 <= i and i < n_);
        return invs[i];
    }

    T dat(int i) const {
        assert(0 <= i and i < n_);
        return data[i];
    }

    int lower_bound(const vector<T>& t) const {
        int l = -1, r = n_;
        while (r - l > 1) {
            int m = (l + r) / 2;
            (lt_substr(t, sa_[m]) ? l : r) = m;
        }
        return r;
    }

    int lower_bound(const string& t) const {
        vector<T> t2 = stovi(t);
        int r = lower_bound(t2);
        return r;
    }

    int upper_bound(vector<T> t) const {
        if (t.empty()) return 0;
        t.back()++;
        int r = lower_bound(t);
        return r;
    }

    int upper_bound(const string& t) const {
        vector<T> t2 = stovi(t);
        int r = upper_bound(t2);
        return r;
    }

    int count(const vector<T>& t) const {
        return upper_bound(t) - lower_bound(t);
    }

    // O(|T|*log|S|)
    int count(const string& t) const {
        vector<T> t2 = stovi(t);
        return count(t2);
    }

  private:
    int n_;
    vector<T> data;
    vector<int> sa_,invs;

    vector<T> stovi(const string& s) const {
        int n = int(s.size());
        vector<T> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i] = s[i];
        }
        return ret;
    }

    bool lt_substr(const vector<T>& t, int pos_s) const {
        int m = int(t.size());
        int pos_t = 0;
        while(pos_s < n_ and pos_t < m) {
            if(data[pos_s] < t[pos_t]) return true;
            if(data[pos_s] > t[pos_t]) return false;
            pos_s++; pos_t++;
        }
        return pos_s == n_ and pos_t < m;
    }

    vector<int> sa_naive(const vector<int>& s) const {
        int n = int(s.size());
        vector<int> sa(n);
        iota(sa.begin(), sa.end(), 0);
        sort(sa.begin(), sa.end(), [&](int l, int r) {
            if (l == r) return false;
            while (l < n && r < n) {
                if (s[l] != s[r]) return s[l] < s[r];
                l++;
                r++;
            }
            return l == n;
        });
        return sa;
    }

    vector<int> sa_doubling(const vector<int>& s) const {
        int n = int(s.size());
        vector<int> sa(n), rnk = s, tmp(n);
        iota(sa.begin(), sa.end(), 0);
        for (int k = 1; k < n; k *= 2) {
            auto cmp = [&](int x, int y) {
                if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
                int rx = x + k < n ? rnk[x + k] : -1;
                int ry = y + k < n ? rnk[y + k] : -1;
                return rx < ry;
            };
            sort(sa.begin(), sa.end(), cmp);
            tmp[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
            }
            swap(tmp, rnk);
        }
        return sa;
    }

    // SA-IS, linear-time suffix array construction
    // Reference:
    // G. Nong, S. Zhang, and W. H. Chan,
    // Two Efficient Algorithms for Linear Time Suffix Array Construction
    template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
    vector<int> sa_is(const vector<int>& s, int upper) const {
        int n = int(s.size());
        if (n == 0) return {};
        if (n == 1) return {0};
        if (n == 2) {
            if (s[0] < s[1]) {
                return {0, 1};
            } else {
                return {1, 0};
            }
        }
        if (n < THRESHOLD_NAIVE) {
            return sa_naive(s);
        }
        if (n < THRESHOLD_DOUBLING) {
            return sa_doubling(s);
        }

        vector<int> sa(n);
        vector<bool> ls(n);
        for (int i = n - 2; i >= 0; i--) {
            ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
        }
        vector<int> sum_l(upper + 1), sum_s(upper + 1);
        for (int i = 0; i < n; i++) {
            if (!ls[i]) {
                sum_s[s[i]]++;
            } else {
                sum_l[s[i] + 1]++;
            }
        }
        for (int i = 0; i <= upper; i++) {
            sum_s[i] += sum_l[i];
            if (i < upper) sum_l[i + 1] += sum_s[i];
        }

        auto induce = [&](const vector<int>& lms) {
            fill(sa.begin(), sa.end(), -1);
            vector<int> buf(upper + 1);
            copy(sum_s.begin(), sum_s.end(), buf.begin());
            for (auto d : lms) {
                if (d == n) continue;
                sa[buf[s[d]]++] = d;
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            sa[buf[s[n - 1]]++] = n - 1;
            for (int i = 0; i < n; i++) {
                int v = sa[i];
                if (v >= 1 && !ls[v - 1]) {
                    sa[buf[s[v - 1]]++] = v - 1;
                }
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            for (int i = n - 1; i >= 0; i--) {
                int v = sa[i];
                if (v >= 1 && ls[v - 1]) {
                    sa[--buf[s[v - 1] + 1]] = v - 1;
                }
            }
        };

        vector<int> lms_map(n + 1, -1);
        int m = 0;
        for (int i = 1; i < n; i++) {
            if (!ls[i - 1] && ls[i]) {
                lms_map[i] = m++;
            }
        }
        vector<int> lms;
        lms.reserve(m);
        for (int i = 1; i < n; i++) {
            if (!ls[i - 1] && ls[i]) {
                lms.push_back(i);
            }
        }

        induce(lms);

        if (m) {
            vector<int> sorted_lms;
            sorted_lms.reserve(m);
            for (int v : sa) {
                if (lms_map[v] != -1) sorted_lms.push_back(v);
            }
            vector<int> rec_s(m);
            int rec_upper = 0;
            rec_s[lms_map[sorted_lms[0]]] = 0;
            for (int i = 1; i < m; i++) {
                int l = sorted_lms[i - 1], r = sorted_lms[i];
                int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
                int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
                bool same = true;
                if (end_l - l != end_r - r) {
                    same = false;
                } else {
                    while (l < end_l) {
                        if (s[l] != s[r]) {
                            break;
                        }
                        l++;
                        r++;
                    }
                    if (l == n || s[l] != s[r]) same = false;
                }
                if (!same) rec_upper++;
                rec_s[lms_map[sorted_lms[i]]] = rec_upper;
            }

            auto rec_sa =
                sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

            for (int i = 0; i < m; i++) {
                sorted_lms[i] = lms[rec_sa[i]];
            }
            induce(sorted_lms);
        }
        return sa;
    }
};

int main() {
    string S; cin >> S;
    SuffixArray<int> SA(S);

    ll ans = 0;
    int M; cin >> M;
    rep(i,M) {
        string T; cin >> T;
        ans += SA.count(T);
    }

    cout << ans << ln;
}
yukicoder

結果

テストケース

ソースコード
