結果

問題 No.430 文字列検索
ユーザー GinatiaGinatia
提出日時 2024-05-31 21:18:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,486 bytes
コンパイル時間 2,795 ms
コンパイル使用メモリ 210,732 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-05-31 21:18:09
合計ジャッジ時間 6,443 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

const int B=3;
const i64 mod[B]={998244353,1000000007,1000000021};
i64 base[B];

using H=std::array<i64,B>;

bool operator==(const H&l,const H&r){
    for(int i=0;i<B;i++){
        if(l[i]!=r[i])return false;
    }
    return true;
}
bool operator!=(const H&l,const H&r){
    for(int i=0;i<B;i++){
        if(l[i]==r[i])return false;
    }
    return true;
}

struct Hash{
    std::vector<std::vector<i64>>ha,pw;

    Hash(const std::string&s){
        int n=s.size();
        ha.assign(B,std::vector<i64>(n+1,0LL));
        pw.assign(B,std::vector<i64>(n+1,1LL));

        for(int k=0;k<B;k++){
            auto&h=ha[k];
            auto&p=pw[k];
            for (int i = 0; i < n; i++) {
                h[i+1]=(h[i]*base[k]+s[i])%mod[k];
                p[i+1]=(p[i]*base[k])%mod[k];
            }
        }
    }
    //S[l:r]
    H get(int l,int r)const{
        H res;
        res.fill(0LL);
        for(int i=0;i<B;i++){
            const auto&h=ha[i];
            const auto&p=pw[i];
            res[i]=h[r]-h[l]*p[r-l];
            res[i]%=mod[i];
            if(res[i]<0)res[i]+=mod[i];
        }
        return res;
    }
    //S
    H get()const{
        H res;
        for(int i=0;i<B;i++)res[i]=ha[i].back();
        return res;
    }

    //lcp(S[a:],S[b:])
    int getLcp(int a,int b)const{
        int len=std::min((int)ha[0].size()-a,(int)ha[0].size()-b);
        int l=0,r=len;
        while(r-l>1){
            int mid=(l+r)>>1;
            if(get(a,a+mid)!=get(b,b+mid))r=mid;
            else l=mid;
        }
        return l;
    }

    //Lcp(S[a:],T[b:])
    int getLcp(const Hash&T,int a,int b)const{
        int len = std::min((int)ha[0].size() - a, (int)ha[0].size() - b);
        int l = 0, r = len;
        while(r-l>1){
            int mid=(l+r)>>1;
            if(get(a,a+mid)!=T.get(b,b+mid))r=mid;
            else l=mid;
        }
        return l;
    }
};

void solve()
{
    std::string s;
    int q;
    std::cin>>s>>q;
    int n=s.size();
    Hash Hs(s);
    i64 ans = 0;
    while(q--){
        std::string t;std::cin>>t;
        Hash Ht(t);
        H ht=Ht.get();
        int m=t.size();
        for(int i=0;i+m-1<n;i++){
            ans+=(ht==Hs.get(i,i+m));
        }
        
    }
    std::cout << ans << '\n';
}
int main()
{

    std::mt19937_64 rng(std::time(0));
    for(int i=0;i<B;i++)base[i]=rng()%mod[i];

    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}
0