結果

問題 No.430 文字列検索
コンテスト
ユーザー Yudai0606Nazo
提出日時 2024-05-19 19:23:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,816 ms / 2,000 ms
コード長 2,136 bytes
コンパイル時間 4,129 ms
コンパイル使用メモリ 254,224 KB
最終ジャッジ日時 2025-02-21 16:03:40
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cassert>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
//using mint = modint1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repu(i, s, t) for (int i = (int)(s); i < (int)(t); i++)
#define repd(i, s, t) for (int i = (int)(s)-1; i >= (int)(t); i--)
#define all(v) v.begin(), v.end()
template<typename T> bool chmax(T &a, const T b) { if(a >= b) return false; a = b; return true; }
template<typename T> bool chmin(T &a, const T b) { if(a <= b) return false; a = b; return true; }
template<typename T> istream& operator>>(istream &in, vector<T> &a) { for(T &x: a) in >> x; return in; }
template<typename T> ostream& operator<<(ostream &out, const vector<T> &a) { for(const T &x: a) out << x << ' '; return out; }
const int di[] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
const int dj[] = {0, 1, 0, -1, -1, 1, 1, -1, 0};


struct KMP {
    int n;
    string s;
    vector<int> skip;
    KMP(string s_) : n(s_.size()), s(s_), skip(int(s_.size())+1) {
        assert(n > 0);
        skip[0] = skip[1] = 0;
        int cur = 0;
        for(int i = 1; i < n; i++) {
            while(cur > 0 && s[i] != s[cur]) cur = skip[cur];
            if(s[i] == s[cur]) cur++;
            skip[i+1] = cur;
        }
    }
    int match(string &t, int ti=0, int cur=0) {
        for(int i = ti; i < int(t.size()); i++) {
            while(cur > 0 && s[cur] != t[i]) cur = skip[cur];
            if(s[cur] == t[i]) cur++;
            if(cur == n) return i-n+1;
        }
        return -1;
    }
    vector<int> all_match(string &t) {
        int ti;
        if((ti = match(t, 0, 0)) < 0) return {};
        vector<int> res(1, ti);
        ti+=n;
        while((ti = match(t, ti, skip.back())) >= 0) {
            res.push_back(ti);
            ti+=n;
        }
        return res;
    }
};

int main() {
    string s;
    int m;
    cin >> s >> m;
    vector<string> c(m);
    cin >> c;

    int ans = 0;
    rep(i, m) {
        KMP ref(c[i]);
        ans += ref.all_match(s).size();
    }
    cout << ans << endl;
    return 0;
}
0