結果

問題 No.430 文字列検索
ユーザー 里旬里旬
提出日時 2019-03-14 04:05:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,974 bytes
コンパイル時間 2,135 ms
コンパイル使用メモリ 206,592 KB
実行使用メモリ 13,632 KB
最終ジャッジ日時 2024-11-10 00:22:40
合計ジャッジ時間 5,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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