結果

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

ソースコード

diff # 

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

using hash_value = pair<vector<uint32_t>, size_t>;
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];
        }
    }
    hash_value 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, s.size()};
    }
    void push_back(hash_value &hvl, char c){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i]*b[i]%p[i]+c) % p[i];
        hvl.second++;
    }
    void push_front(hash_value &hvl, char c){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i] + mpow(b[i], hvl.second, p[i])*c%p[i]) % p[i];
        hvl.second++;
    }
    void pop_back(hash_value &hvl, char c){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i]+p[i]-c%p[i]) * mpow(b[i], p[i]-2, p[i]) % p[i];
        hvl.second--;
    }
    void pop_front(hash_value &hvl, char c){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i] + p[i] - c*mpow(b[i], hvl.second-1, p[i])%p[i]) % p[i];
        hvl.second--;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    string s;
    int m;
    string c[5000];
    cin >> s;
    cin >> m;
    for(int i=0;i<m;i++) cin >> c[i];

    rolling_hash rh;
    hash_value hash_s, hash_c;
    int ans = 0;
    for(int i=0;i<m;i++){
        hash_c = rh(c[i]);
        if(s.size() < c[i].size()) continue;
        hash_s = rh(s.substr(0, c[i].size()));
        if(hash_s == hash_c) ans++;
        for(size_t pos = c[i].size();pos<s.size();pos++){
            rh.pop_front(hash_s, s[pos-c[i].size()]);
            rh.push_back(hash_s, s[pos]);
            if(hash_s == hash_c) ans++;
        }
    }

    cout << ans << endl;
    
    return 0;
}
0