結果

問題 No.430 文字列検索
ユーザー hedwig100hedwig100
提出日時 2020-08-13 15:12:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 395 ms / 2,000 ms
コード長 2,058 bytes
コンパイル時間 1,950 ms
コンパイル使用メモリ 176,752 KB
実行使用メモリ 27,136 KB
最終ジャッジ日時 2024-04-18 01:31:59
合計ジャッジ時間 4,071 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 395 ms
27,136 KB
testcase_02 AC 12 ms
5,376 KB
testcase_03 AC 12 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 375 ms
26,880 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 17 ms
6,144 KB
testcase_11 AC 98 ms
7,936 KB
testcase_12 AC 101 ms
8,064 KB
testcase_13 AC 102 ms
8,064 KB
testcase_14 AC 72 ms
6,528 KB
testcase_15 AC 56 ms
5,632 KB
testcase_16 AC 16 ms
5,376 KB
testcase_17 AC 13 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

using u64 = unsigned long long;
constexpr u64 M = 2305843009213693951; // 2^61 - 1
constexpr u64 MASK31 = 2147483647; // 2^31 - 1
constexpr u64 POSITIVIZER = 4*M;

u64 CalcMod(u64 x) {
    u64 res = (x >> 61) + (x&M);
    if (res >= M) res -= M;
    return res;
}
u64 mul(u64 x,u64 y) {
    u64 au = (x >> 31),ad = (x&MASK31),bu = (y >> 31),bd = (y&MASK31);
    u64 m = au * bd + ad * bu;
    u64 mu = (m >> 31),md = (m&MASK31);
    u64 ans = 2*au*bu + 2*mu + (md << 31) + ad*bd;
    return CalcMod(ans);
}

struct RollingHash {
    static u64 B;
    int N;
    vector<u64> hash,power;
    RollingHash(const string &s) {
        N = (int)s.size();
        hash.resize(N + 1,0); power.resize(N + 1,0);
        hash[0] = 0; power[0] = 1;
        for (int i = 0; i < (int)s.size(); ++i) {
            hash[i + 1] = CalcMod(mul(hash[i],B) + s[i]);
            power[i + 1] = mul(power[i],B);
        }
    }
    u64 get() {return hash[N];}
    u64 get(int k) {return hash[k];}
    u64 get(int l,int r) {return CalcMod(hash[r] + POSITIVIZER - mul(hash[l],power[r - l]));}
};

mt19937_64 mt;
uniform_int_distribution<unsigned long long> rng(2,M - 2);
unsigned long long RollingHash::B = rng(mt);

int main() {
    string S; cin >> S;
    RollingHash rh(S);
    map<u64,ll> mp;
    for (int l = 0;l < S.size(); ++l) {
        for (int r = l + 1;r <= min(l + 10,(int)S.size()); ++r) {
            u64 x = rh.get(l,r);
            mp[x] ++;
        }
    }
    ll ans = 0;
    int M; cin >> M;
    rep(i,M) {
        string a; cin >> a;
        RollingHash rha(a);
        ans += mp[rha.get()];
    }
    cout << ans << '\n';
    return 0;
}
0