結果

問題 No.430 文字列検索
ユーザー 里旬里旬
提出日時 2019-03-13 10:05:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,515 bytes
コンパイル時間 2,516 ms
コンパイル使用メモリ 210,392 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-10 00:22:39
合計ジャッジ時間 5,566 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>, size_t>;
class rolling_hash{
    mt19937 mt;
    const uint32_t p[3] = {2111511013, 2131131137, 2147483647};
    const int P_CNT = 1;
    uint64_t b[3], binv[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];
            binv[i] = mpow(b[i], p[i]-2, p[i]);
        }
    }
    hash_value operator()(string s){
        vector<uint32_t> h = {0, 0, 0};
        for(char c : s){
            for(int i=0;i<P_CNT;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<P_CNT;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<P_CNT;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<P_CNT;i++) hv[i] = (hv[i]+p[i]-c%p[i]) * binv[i] % p[i];
        hvl.second--;
    }
    void pop_front(hash_value &hvl, char c){
        auto &hv = hvl.first;
        for(int i=0;i<P_CNT;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("");
        for(size_t j=0;j<c[i].size();j++) rh.push_back(hash_s, s[j]);
        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.first == hash_c.first) ans++;
        }
    }

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