結果

問題 No.430 文字列検索
ユーザー karinohitokarinohito
提出日時 2022-05-20 13:45:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 3,541 bytes
コンパイル時間 2,431 ms
コンパイル使用メモリ 216,952 KB
実行使用メモリ 24,096 KB
最終ジャッジ日時 2023-10-20 01:46:52
合計ジャッジ時間 3,604 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 105 ms
24,096 KB
testcase_02 AC 13 ms
8,060 KB
testcase_03 AC 14 ms
8,060 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 20 ms
10,160 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 26 ms
9,896 KB
testcase_12 AC 20 ms
9,104 KB
testcase_13 AC 19 ms
9,104 KB
testcase_14 AC 17 ms
8,588 KB
testcase_15 AC 16 ms
8,324 KB
testcase_16 AC 14 ms
8,088 KB
testcase_17 AC 14 ms
8,060 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
using pqr = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>;

vector<ll> fact, factinv, inv;
ll mod = 998244353;
void prenCkModp(ll n) {
    fact.resize(n + 5);
    factinv.resize(n + 5);
    inv.resize(n + 5);
    fact.at(0) = fact.at(1) = 1;
    factinv.at(0) = factinv.at(1) = 1;
    inv.at(1) = 1;
    for (ll i = 2; i < n + 5; i++) {
        fact.at(i) = (fact.at(i - 1) * i) % mod;
        inv.at(i) = mod - (inv.at(mod % i) * (mod / i)) % mod;
        factinv.at(i) = (factinv.at(i - 1) * inv.at(i)) % mod;
    }

}
ll nCk(ll n, ll k) {
    if (n < k) return 0;
    return fact.at(n) * (factinv.at(k) * factinv.at(n - k) % mod) % mod;
}

bool chmax(ll& p, ll q) {
    if (p < q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}

bool chmin(ll& p, ll q) {
    if (p > q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}

ll sti(string S) {
    ll res = 0;
    rep(i, S.size()) {
        res += S[i] - '0';
        res *= 10;
    }
    return res / 10;
}

string ist(ll n, ll L) {
    string res = "";
    rep(l, L)res += '0';
    ll p = L - 1;
    while (n > 0) {
        res[p] = char(n % 10 + '0');
        p--;
        n /= 10;
    }
    return res;
}

ll gcd(ll(a), ll(b)) {
    ll c = a;
    while (a % b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return b;
}

struct rollinghash{
    const ll base=9973;
    const vector<ll> MoD = {999999937, 1000000007};
    string S;
    vector<ll> hash[2], power[2];
    rollinghash(const string &cs) { init(cs); }

    ll Shash(string T,ll iter){
        ll n = T.size();
        ll reshash=0;
        ll respow=1;
        rep(i,n){
            reshash = (reshash*base + T[i]) % MoD[iter];
        }
        return reshash;
    }

    void init(const string &cs) {
        S = cs;
        ll n = S.size();
        rep(iter,MoD.size()) {
            hash[iter].assign(n+1, 0);
            power[iter].assign(n+1, 1);
            rep(i,n) {
                hash[iter][i+1] = (hash[iter][i] * base + S[i]) % MoD[iter];
                power[iter][i+1] = power[iter][i] * base % MoD[iter];
            }
        }
    }
    ll get(int l, int r, int id = 0) const {
        return ((hash[id][r] - (hash[id][l] * power[id][r-l]) % MoD[id])+MoD[id])%MoD[id];
    }
    ll getLCP(int a, int b) const {
        int len = min((int)S.size()-a, (int)S.size()-b);
        int low = -1, high = len + 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (get(a, a+mid, 0) != get(b, b+mid, 0)) high = mid;
            else if (get(a, a+mid, 1) != get(b, b+mid, 1)) high = mid;
            else low = mid;
        }
        return low;
    }
};



int main() {
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);

    string S;
    cin>>S;
    rollinghash rh(S);

    ll N=S.size();
    ll M;
    cin>>M;
    ll an=0;
    vector<unordered_map<ll,ll>> D(S.size()+1);
    rep(m,M){
        string T;
        cin>>T;
        ll P=T.size();
        ll CH=rh.Shash(T,0);
        if(N<P)continue;
        if(D[P].size()==0)rep(i,N){
            if(i+P>N)break;
            ll CB=rh.get(i,i+P);
            D[P][CB]++;
        }
        an+=D[P][CH];
    }
    cout<<an<<endl;

}
0