#383725 (C++11) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: 🍮かんプリン
• 提出日時: 2019-09-27 16:54:38
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 17 ms / 2,000 ms
• コード長: 5,137 bytes
• コンパイル時間: 1,570 ms
• コンパイル使用メモリ: 171,264 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-10 00:34:37
• 合計ジャッジ時間: 2,390 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	16 ms; 5,248 KB
testcase_02	AC	11 ms; 5,248 KB
testcase_03	AC	11 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	14 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	17 ms; 5,248 KB
testcase_12	AC	17 ms; 5,248 KB
testcase_13	AC	17 ms; 5,248 KB
testcase_14	AC	17 ms; 5,248 KB
testcase_15	AC	17 ms; 5,248 KB
testcase_16	AC	13 ms; 5,248 KB
testcase_17	AC	13 ms; 5,248 KB

ソースコード

#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;
}