結果

問題 No.430 文字列検索
コンテスト
ユーザー 里旬
提出日時 2019-03-14 04:05:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,974 bytes
コンパイル時間 1,931 ms
コンパイル使用メモリ 201,056 KB
最終ジャッジ日時 2025-01-06 22:07:51
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class rolling_hash{
    mt19937 mt;
    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;
    }
public:
    rolling_hash(){
        random_device rd;
        mt.seed(rd());
        for(int i=0;i<3;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(int i=0;i<3;i++) h[i] = (h[i]*b[i]%p[i]+c) % p[i];
        }
        return h;
    }
    // x が y の中に何回出現するか
    uint32_t contain(const string &x, const string &y){
        size_t xl = x.size(), yl = y.size();
        if(xl > yl) return 0;
        uint64_t bl[3];
        for(int i=0;i<3;i++) bl[i] = mpow(b[i], xl, p[i]);

        vector<uint32_t> xh(3, 0), yh(3, 0);
        for(int i=0;i<3;i++){
            for(size_t j=0;j<xl;j++) xh[i] = (xh[i]*b[i]%p[i] + x[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++){
            if(xh == yh) cnt++;
            if(pos + xl < yl)
                for(int i=0;i<3;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];

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