結果

問題 No.430 文字列検索
ユーザー 里旬里旬
提出日時 2019-03-14 04:33:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 296 ms / 2,000 ms
コード長 2,646 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 209,672 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-07 08:16:01
合計ジャッジ時間 6,243 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 294 ms
4,384 KB
testcase_02 AC 296 ms
4,380 KB
testcase_03 AC 295 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 7 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 4 ms
4,380 KB
testcase_11 AC 294 ms
4,380 KB
testcase_12 AC 288 ms
4,380 KB
testcase_13 AC 291 ms
4,380 KB
testcase_14 AC 289 ms
4,376 KB
testcase_15 AC 292 ms
4,380 KB
testcase_16 AC 294 ms
4,380 KB
testcase_17 AC 290 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class rolling_hash{
    mt19937 mt;
    const size_t p_cnt = 3;
    const uint32_t p[3] = {2111511013, 2131131137, 2147483647};
    uint64_t b[3];

    uint64_t mpow(uint64_t x, uint64_t y, uint32_t m){
        if(y == 0) return 1;
        if(y == 1) return x%m;
        if(y%2 == 0) return mpow(x*x%m, y/2, m);
        return mpow(x*x%m, y/2, m) * x % m;
    }
    bool is_equal(const vector<uint32_t> &x, const vector<uint32_t> &y){
        for(size_t i=0;i<p_cnt;i++){
            if(x[i] != y[i]) return false;
        }
        return true;
    }
public:
    rolling_hash(){
        random_device rd;
        mt.seed(rd());
        for(size_t i=0;i<p_cnt;i++){
            b[i] = 0; 
            while(!b[i]) b[i] = mt() % p[i];
        }
    }
    vector<uint32_t> operator()(string s){
        vector<uint32_t> h = {0, 0, 0};
        for(char c : s){
            for(size_t i=0;i<p_cnt;i++) h[i] = (h[i]*b[i]%p[i]+c) % p[i];
        }
        return h;
    }
    // x が y の中に何回出現するか
    uint32_t contain(const vector<string> &xs, const string &y){
        if(xs.size() == 0) return 0;
        size_t xl = xs[0].size(), yl = y.size();
        if(xl > yl) return 0;
        uint64_t bl[p_cnt];
        for(size_t i=0;i<p_cnt;i++) bl[i] = mpow(b[i], xl, p[i]);

        vector<vector<uint32_t>> xhs(xs.size());
        for(size_t i=0;i<xs.size();i++) xhs[i] = vector<uint32_t>(p_cnt, 0);
        vector<uint32_t> yh(3, 0);
        for(size_t i=0;i<p_cnt;i++){
            for(size_t xi=0;xi<xs.size();xi++)
                for(size_t j=0;j<xl;j++) xhs[xi][i] = (xhs[xi][i]*b[i]%p[i] + xs[xi][j]) % p[i];
            for(size_t j=0;j<xl;j++) yh[i] = (yh[i]*b[i]%p[i] + y[j]) % p[i];
        }

        uint32_t cnt = 0;
        for(size_t pos=0;pos+xl<=yl;pos++){
            for(size_t xi=0;xi<xs.size();xi++){
                if(is_equal(xhs[xi], yh)) cnt++;
            }
            if(pos + xl < yl)
                for(size_t i=0;i<p_cnt;i++) yh[i] = (yh[i]*b[i]%p[i] + y[xl+pos] +p[i] - y[pos]*bl[i]%p[i]) % p[i];
        }

        return cnt;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    rolling_hash rh;
    string s, c[5000];
    int m;

    cin >> s;
    cin >> m;
    for(int i=0;i<m;i++) cin >> c[i];

    vector<string> cs[11];
    for(int i=0;i<m;i++){
        cs[c[i].size()].push_back(c[i]);
    }

    uint64_t ans = 0;
    for(int i=1;i<=10;i++){
        ans += rh.contain(cs[i], s);
    }
    cout << ans << endl;
    
    return 0;
}
0