結果

問題 No.430 文字列検索
ユーザー hedwig100hedwig100
提出日時 2020-08-11 22:56:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 2,473 bytes
コンパイル時間 1,554 ms
コンパイル使用メモリ 180,752 KB
実行使用メモリ 27,904 KB
最終ジャッジ日時 2024-11-10 00:45:44
合計ジャッジ時間 3,029 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 252 ms
27,904 KB
testcase_02 AC 12 ms
6,816 KB
testcase_03 AC 12 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 1 ms
6,824 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 246 ms
27,648 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 15 ms
6,820 KB
testcase_11 AC 83 ms
8,832 KB
testcase_12 AC 84 ms
8,832 KB
testcase_13 AC 85 ms
8,832 KB
testcase_14 AC 65 ms
7,296 KB
testcase_15 AC 51 ms
6,820 KB
testcase_16 AC 14 ms
6,816 KB
testcase_17 AC 13 ms
6,816 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;


struct RollingHash {
    using u64 = unsigned long long;
    static const u64 M1 = 2147483647,M2 = 1000000007;
    static u64 B1,B2;
    int N;
    vector<u64> hash1,hash2,power1,power2;

    RollingHash(string &s) {
        N = s.size();
        power1.resize(N + 1); power2.resize(N + 1); hash1.resize(N + 1); hash2.resize(N + 1);
        power1[0] = 1;        power2[0] = 1;        hash1[0] = 0;        hash2[0] = 0;
        for (int i = 0;i < N; ++i) {
            power1[i + 1] = power1[i] * B1 % M1;
            power2[i + 1] = power2[i] * B2 % M2;
            hash1[i + 1] = (hash1[i] * B1 + s[i]) % M1;
            hash2[i + 1] = (hash2[i] * B2 + s[i]) % M2;
        }
    }
    // retunr hash of S
    pair<u64,u64> get() {
        return make_pair(hash1[N],hash2[N]);
    }
    // return hash of S[0,k)
    pair<u64,u64> get(int k) {
        return make_pair(hash1[k],hash2[k]);
    }
    // return hash of S[l,r)
    pair<u64,u64> get(int l,int r) {
        u64 x = (hash1[r] - (hash1[l] * power1[r - l]) % M1 + M1) % M1;
        u64 y = (hash2[r] - (hash2[l] * power2[r - l]) % M2 + M2) % M2;
        return make_pair(x,y);
    }
    //return if S[l1,r1) == S[l2,r2)
    bool equal(int l1,int r1,int l2,int r2) {
        return get(l1,r1) == get(l2,r2);
    }
};

mt19937_64 mt;
uniform_int_distribution<unsigned long long> rand1(1,RollingHash::M1 - 1);
uniform_int_distribution<unsigned long long> rand2(1,RollingHash::M2 - 1);
unsigned long long RollingHash::B1 = rand1(mt);
unsigned long long RollingHash::B2 = rand2(mt);

using u64 = unsigned long long;
using Pu = pair<u64,u64>;

int main() {
    string S; cin >> S;
    RollingHash rh(S);
    map<Pu,ll> mp;
    for (int l = 0;l < S.size(); ++l) {
        for (int r = l + 1;r <= min(l + 10,(int)S.size()); ++r) {
            Pu x = rh.get(l,r);
            mp[rh.get(l,r)] ++;
        }
    }
    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