結果

問題 No.430 文字列検索
ユーザー kenta255
提出日時 2019-08-29 10:06:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 731 bytes
コンパイル時間 1,965 ms
コンパイル使用メモリ 198,448 KB
最終ジャッジ日時 2025-01-07 15:32:15
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
struct RollingHash{
    ll M;
    vector<ll> H,B;
    RollingHash(string s,ll b=1009LL,ll m=1000000007LL){
        M = m;
        ll n = s.size();
        B.resize(n+1);
        H.resize(n+1,0);
        B[0] = 1;
        for(ll i=0;i<n;i++){
            B[i+1] = (B[i]*b)%M;
            H[i+1] = (H[i]*b%M+s[i])%M;
        }
    }
    ll GetHash(ll l,ll r){ // [l,r)
        return (H[r]+(M-B[r-l]*H[l]%M))%M;
    }
};
int main(){
    string S,C;
    ll M,ans=0,Sl;
    cin >> S >> M;
    Sl = S.size();
    RollingHash Shash(S);
    for(int i=0;i<M;i++){
        cin >> C;
        RollingHash Chash(C);
        ll cl = C.size();
        ll ch = Chash.GetHash(0,cl);
        for(int j=0;j<Sl-cl+1;j++){
            ans += ch == Shash.GetHash(j,j+cl);
        }
    }
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0