結果

問題 No.430 文字列検索
コンテスト
ユーザー minato
提出日時 2020-01-09 21:46:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 957 ms / 2,000 ms
コード長 2,263 bytes
コンパイル時間 2,082 ms
コンパイル使用メモリ 182,664 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:40:10
合計ジャッジ時間 12,401 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
const double PI = acos(-1);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

struct RollingHash {
    typedef unsigned long long ull;

    const ull MASK30 = (1ull << 30) - 1;
    const ull MASK31 = (1ull << 31) - 1;
    const ull mod = (1ull << 61) - 1;
    const ull POSITIVIZER = mod * 3;
    const ull base = 10007;

    vector<ull> hash,power;

    RollingHash(const string &s) {
        int sz = s.size();
        hash.assign(sz + 1,0);
        power.assign(sz + 1,1);
        for (int i = 0; i < sz; i++) {
            power[i+1] = CalcMod(Mul(power[i],base));
            hash[i+1] = CalcMod(Mul(hash[i],base) + s[i]);
        }
    }

    ull get(int l, int r) {
        ull res;
        res = CalcMod(hash[r] + POSITIVIZER - Mul(hash[l],power[r-l]));
        return res;
    }


    ull Mul (ull a, ull b) {
        ull au = a >> 31;
        ull ad = a & MASK31;
        ull bu = b >> 31;
        ull bd = b & MASK31;
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & MASK30;
        return (au * bu * 2 + midu + (midd << 31) + ad * bd);
    }

    ull CalcMod(ull val) {
        val = (val & mod) + (val >> 61);
        if (val > mod) val -= mod;
        return val;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string S; cin >> S;
    int N = S.size();
    int M; cin >> M;
    vector<string> C(M);
    rep(i,M) cin >> C[i];

    RollingHash RH(S);
    int cnt = 0;
    rep(i,M) {
        int K = C[i].size();
        RollingHash rh(C[i]);
        rep(j,N-K+1) {
            if (RH.get(j,j+K) == rh.get(0,K)) cnt++;
        }
    }

    cout << cnt << endl;
}
0