結果

問題 No.430 文字列検索
ユーザー 里旬里旬
提出日時 2019-03-13 09:42:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,520 bytes
コンパイル時間 2,625 ms
コンパイル使用メモリ 210,388 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-10 00:22:28
合計ジャッジ時間 5,750 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 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;

using hash_value = pair<vector<uint32_t>, string>;
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};
    }
    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.push_back(c);
    }
    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.size(), p[i])*c%p[i]) % p[i];
        hvl.second = c + hvl.second;
    }
    void pop_back(hash_value &hvl){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i]+p[i]-hvl.second.back())%p[i] * mpow(b[i], p[i]-2, p[i]) % p[i];
        hvl.second.pop_back();
    }
    void pop_front(hash_value &hvl){
        auto &hv = hvl.first;
        for(int i=0;i<3;i++) hv[i] = (hv[i] + p[i] - hvl.second[0]*mpow(b[i], hvl.second.size()-1, p[i])%p[i]) % p[i];
        hvl.second.erase(hvl.second.begin());
    }
};
bool operator==(const hash_value &a, const hash_value &b){
    return a.first == b.first;
}

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);
            rh.push_back(hash_s, s[pos]);
            if(hash_s == hash_c) ans++;
        }
    }

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