結果

問題 No.430 文字列検索
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2019-09-27 16:54:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 5,137 bytes
コンパイル時間 1,733 ms
コンパイル使用メモリ 172,916 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-24 16:57:32
合計ジャッジ時間 2,826 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include "bits/stdc++.h"
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = MOD - 1;
const ll LLINF = 4e18;

// <O(NlogN),O(1)>
template< typename T >
struct SparseTable {
    using Func = function<T(T, T)>;
    vector< vector< T > > st;
    vector< int > lookup;
    Func F;// min or max

    SparseTable() {}

    SparseTable(const vector< T > &v, Func F) : F(F) {
        int b = 0;
        while ((1 << b) <= v.size()) ++b;
        st.assign(b, vector< T >(1 << b));
        REP(i, v.size()) st[0][i] = v[i];
        FOR(i, 1, b) for (int j = 0; j + (1 << i) <= (1 << b); j++) st[i][j] = F(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        lookup.resize(v.size() + 1);
        FOR(i, 2, lookup.size()) lookup[i] = lookup[i >> 1] + 1;
    }

    // [l,r)
    inline T rmq(int l, int r) {
        int b = lookup[r - l];
        return F(st[b][l], st[b][r - (1 << b)]);
    }
};

struct SuffixArray {
private:
    vector< int > SA, LCP;
    vector<int> rank;// rank[i]:s[i:]のSAのindex
    string s;
    SparseTable<int> st;

    // 比較関数 s[si:] < t[ti:]
    bool lt_substr(string& t, int si = 0, int ti = 0)
    {
        int sn = s.size(), tn = t.size();
        while (si < sn && ti < tn) {
            if (s[si] < t[ti]) return (true);
            if (s[si] > t[ti]) return (false);
            ++si, ++ti;
        }
        return (si >= sn && ti < tn);
    }

    // prefixがtの辞書順最小
    // O(|t|log|S|)
    int lower_bound(string& t)
    {
        int low = -1, high = SA.size();
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (lt_substr(t, SA[mid])) low = mid;
            else high = mid;
        }
        return high;
    }

    // [first,second) のprefixがt
    // O(|t|log|S|)
    pair<int, int> lower_upper_bound(string& t) {
        int idx = lower_bound(t);
        int low = idx - 1, high = SA.size();
        t.back()++;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (lt_substr(t, SA[mid])) low = mid;
            else high = mid;
        }
        t.back()--;
        return {idx, high};
    }
public:

    SuffixArray(const string& str) : s(str)
    {
        SA.resize(s.size());
        iota(begin(SA), end(SA), 0);
        sort(begin(SA), end(SA), [&](const int& a, const int& b)
        {
            if (s[a] == s[b]) return(a > b);
            return (s[a] < s[b]);
        });
        vector< int > classes(s.size()), c(s.size()), cnt(s.size());
        for (int i = 0; i < s.size(); i++) {
            c[i] = s[i];
        }
        for (int len = 1; len < s.size(); len <<= 1) {
            for (int i = 0; i < s.size(); i++) {
                if (i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
                    classes[SA[i]] = classes[SA[i - 1]];
                }
                else {
                    classes[SA[i]] = i;
                }
            }
            iota(begin(cnt), end(cnt), 0);
            copy(begin(SA), end(SA), begin(c));
            for (int i = 0; i < s.size(); i++) {
                int s1 = c[i] - len;
                if (s1 >= 0) SA[cnt[classes[s1]]++] = s1;
            }
            classes.swap(c);
        }
    }

    int count(string &t) {
        pair<int, int> p = lower_upper_bound(t);
        return p.second - p.first;
    }

    // s中のtの位置 
    // 順番は適当 ソートしてない
    vector<int> find(string &t) {
        vector<int> v;
        pair<int, int> p = lower_upper_bound(t);
        FOR(i, p.first, p.second) {
            v.push_back(SA[i]);
        }
        return v;
    }

    void print_sa() {
        REP(i, s.size()) cout << i << ": " << s.substr(SA[i]) << endl;
    }

    // O(|S|)
    void build_lcp() {
        rank.resize(s.size());
        REP(i, s.size()) rank[SA[i]] = i;
        LCP.resize(s.size());
        LCP[0] = 0;
        for (int i = 0, h = 0; i < s.size(); i++) {
            if (rank[i] + 1 < s.size()) {
                for (int j = SA[rank[i] + 1]; max(i, j) + h < s.length() && s[i + h] == s[j + h]; ++h);
                LCP[rank[i] + 1] = h;
                if (h > 0) --h;
            }
        }
        st = SparseTable<int>(LCP, [](int x, int y) {return min(x, y); });
    }

    void print_lcp() {
        cout << "No.\tLCP\tsuffix" << endl;
        cout << "----------------------" << endl;
        REP(i, s.size()) cout << i << ":\t" << LCP[i] << "\t" << s.substr(SA[i]) << endl;
    }

    // s[a:]とs[b:]のLCP
    int get_lcp(int a, int b) {
        if (a == b) return s.substr(a).size();
        return st.rmq(min(rank[a], rank[b]) + 1, max(rank[a], rank[b]) + 1);
    }
};

int main() {
    string s; cin >> s;
    SuffixArray sa(s);
    int m; cin >> m;
    ll ans = 0;
    REP(i,m) {
        string c; cin >> c;
        ans += sa.count(c);
    }
    cout << ans << endl;
}
0