結果

問題 No.430 文字列検索
ユーザー yuto1115yuto1115
提出日時 2020-06-10 00:26:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 4,072 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 215,864 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:44:34
合計ジャッジ時間 2,729 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 36 ms
5,248 KB
testcase_02 AC 8 ms
5,248 KB
testcase_03 AC 8 ms
5,248 KB
testcase_04 AC 1 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 7 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 13 ms
5,248 KB
testcase_13 AC 13 ms
5,248 KB
testcase_14 AC 13 ms
5,248 KB
testcase_15 AC 13 ms
5,248 KB
testcase_16 AC 9 ms
5,248 KB
testcase_17 AC 9 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

using ull = unsigned long long;
const ull mod = (1ul<<61)-1;
const ull mask30 = (1ul<<30)-1;
const ull mask31 = (1ul<<31)-1;
const ull mask61 = mod;

ull calc_mod(ull x) {
    ull xu = x>>61;
    ull xd = x&mask61;
    ull res = xu+xd;
    if(res >= mod) res -= mod;
    return res;
}

// a*b mod 2^61-1
ull mul(ull a,ull b) {
    ull au = a>>31;
    ull ad = a&mask31;
    ull bu = b>>31;
    ull bd = b&mask31;
    ull mid = ad*bu+au*bd;
    ull midu = mid>>30;
    ull midd = mid&mask30;
    return au*bu*2+midu+(midd<<31)+ad*bd;
}

class rolling_hash {
    ull base1;
    ull base2;
    int n;
    string s;
    vector<ull> hash1,hash2,pow1,pow2;

    void init() {
        random_device rnd;
        mt19937_64 mt(rnd());
        base1 = calc_mod(mt());
        base2 = calc_mod(mt());
        while(base1 < 2 || base1 > mod-2) base1 = calc_mod(mt());
        while(base2 < 2 || base2 > mod-2) base2 = calc_mod(mt());
        hash1.assign(n+1,0);
        hash2.assign(n+1,0);
        pow1.assign(n+1, 1);
        pow2.assign(n+1,1);
        rep(i,n) {
            hash1[i+1] = calc_mod(mul(hash1[i],base1)+s[i]);
            hash2[i+1] = calc_mod(mul(hash2[i],base2)+s[i]);
            pow1[i+1] = calc_mod(mul(pow1[i], base1));
            pow2[i+1] = calc_mod(mul(pow2[i], base2));
        }
    }

public:
    rolling_hash(string s):s(s),n(s.size()) {
        init();
    }
    // return hash of [l,r) of S
    pair<ull,ull> get(int l,int r) {
        ll res1 = calc_mod(hash1[r]+mod*4-mul(hash1[l], pow1[r-l]));
        ll res2 = calc_mod(hash2[r]+mod*4-mul(hash2[l], pow2[r-l]));
        return make_pair(res1,res2);
    }
    // return hash of T
    pair<ull,ull> get(string t) {
        ull ht1 = 0,ht2 = 0;
        rep(i,t.size()) {
            ht1 = calc_mod(mul(ht1,base1)+t[i]);
            ht2 = calc_mod(mul(ht2,base2)+t[i]);
        }
        return make_pair(ht1,ht2);
    }
    int count(string t) {
        if(t.size() > n) return 0;
        pair<ull,ull> ht = get(t);
        int res = 0;
        rep(i,n-t.size()+1) {
            if(get(i,i+t.size()) == ht) res++;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    string s;
    int m;
    cin >> s >> m;
    rolling_hash rh(s);
    int ans = 0;
    vector<set<pair<ull,ull>>> v(11);
    rep(i,m) {
        string c;
        cin >> c;
        v[c.size()].insert(rh.get(c));
    }
    rep2(i,1,11) {
        if(i > s.size()) break;
        rep(j,s.size()-i+1) {
            auto r = rh.get(j,j+i);
            if(v[i].count(r)) ans++;
        }
    }
    cout << ans << endl;
}
0