結果

問題 No.430 文字列検索
コンテスト
ユーザー ゆにぽけ
提出日時 2023-07-29 10:52:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,267 ms / 2,000 ms
コード長 2,223 bytes
コンパイル時間 706 ms
コンパイル使用メモリ 86,548 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 01:07:05
合計ジャッジ時間 13,814 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<random>
#include<ctime>
#include<vector>
#include<cassert>
using namespace std;

struct RollingHash
{
    static const unsigned long mod = (1UL << 61) - 1;
    static unsigned long base;
    int n;
    vector<unsigned long> hashed,pow;

    inline unsigned long mul(unsigned long a,unsigned long b) const
    {
        unsigned long au = a >> 31;
        unsigned long ad = a & ((1UL << 31)-1);
        unsigned long bu = b >> 31;
        unsigned long bd = b & ((1UL << 31)-1);
        unsigned long mid = au*bd + bu*ad;
        unsigned long midu = mid >> 30;
        unsigned long midd = mid & ((1UL << 30)-1);

        unsigned long res = au*bu*2 + midu + (midd << 31) + ad*bd;

        res = (res >> 61) + (res & mod);
        if(res >= mod) res -= mod;

        return res;
    }

    RollingHash(string &s)
    {
        n = (int)s.size();
        hashed.resize(n+1);
        pow.resize(n+1);

        pow[0] = 1;
        for(int i = 0;i < n;i++)
        {
            pow[i+1] = mul(pow[i],base);
            hashed[i+1] = mul(hashed[i],base) + s[i];

            if(hashed[i+1] >= mod) hashed[i+1] -= mod;
        }
    }

    unsigned long get() const {return get(0,n);}

    unsigned long get(int l,int r) const
    {
        assert(0 <= l && l <= r && r <= n);

        unsigned long res = hashed[r] + mod - mul(hashed[l],pow[r-l]);
        if(res >= mod) res -= mod;

        return res;
    }

    unsigned long connect(int l1,int r1,int l2,int r2) const
    {
        unsigned long h1 = get(l1,r1);
        unsigned long h2 = get(l2,r2);

        unsigned long res = h2 + mul(h1,pow[r2-l2]);

        if(res >= mod) res -= mod;

        return res;
    }
};

mt19937_64 mt{(unsigned int)time(nullptr)};
unsigned long RollingHash::base = mt()%RollingHash::mod;

string s;
int m;

int main()
{
    cin >> s >> m;

    RollingHash H(s);

    int ans = 0;
    while(m--)
    {
        string c;
        cin >> c;

        int l = (int)c.size();

        RollingHash h(c);
        unsigned long x = h.get();


        for(int i = 0;i+l <= (int)s.size();i++)
        {
            unsigned long y = H.get(i,i+l);
            if(x == y) ans++;
        }
    }

    cout << ans << endl;
}
0