結果

問題 No.430 文字列検索
ユーザー ゆにぽけゆにぽけ
提出日時 2023-07-29 10:52:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,136 ms / 2,000 ms
コード長 2,223 bytes
コンパイル時間 1,027 ms
コンパイル使用メモリ 87,168 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-16 17:25:27
合計ジャッジ時間 12,933 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1,123 ms
5,376 KB
testcase_02 AC 1,129 ms
5,376 KB
testcase_03 AC 1,131 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 1,126 ms
5,376 KB
testcase_12 AC 1,136 ms
5,376 KB
testcase_13 AC 1,128 ms
5,376 KB
testcase_14 AC 1,125 ms
5,376 KB
testcase_15 AC 1,129 ms
5,376 KB
testcase_16 AC 1,127 ms
5,376 KB
testcase_17 AC 1,128 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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