結果

問題 No.430 文字列検索
コンテスト
ユーザー takey
提出日時 2024-05-24 03:36:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 479 ms / 2,000 ms
コード長 3,070 bytes
コンパイル時間 5,460 ms
コンパイル使用メモリ 278,644 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 01:11:21
合計ジャッジ時間 10,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES  // M_PI等のフラグ
#include <bits/stdc++.h>
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define intceil(a,b) ((a+(b-1))/(b))
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long,long>;
const long long INF = LONG_LONG_MAX - 1001001001001001;
void chmax(ll& x, ll y) { x = max(x,y); }
void chmin(ll& x, ll y) { x = min(x,y); }
string vs = "URDL";  // 上右下左
vector<ll> vy = { -1, 0, 1, 0 };
vector<ll> vx = { 0, 1, 0, -1 };

/***ローリングハッシュ法で文字列検索
 * 計算量はO(N+M)
 ***/
const unsigned long long B = 100000007;  // ハッシュの基数

/***文字列s1はs2に含まれているか？
 * Returns:
 *  含まれている場合、一致箇所の開始位置であるs2のインデックスを返す
 *  含まれていなかった場合、-1を返す
 **/
long long contain(string s1, string s2) {
    long long s1_len = s1.length();
    long long s2_len = s2.length();

    if (s1_len > s2_len) return -1;

    // Bのs1_len乗を計算する
    unsigned long long t = 1;
    for (long long i=0; i<s1_len; i++) t *= B;

    // s1とs2の最初のs1_len文字に関するハッシュ値を計算する
    unsigned long long s1h = 0, s2h = 0;  // ハッシュ値
    for (long long i=0; i<s1_len; i++) s1h = s1h * B + s1[i];
    for (long long i=0; i<s1_len; i++) s2h = s2h * B + s2[i];

    // s2の場所を1つずつ進めながらハッシュ値をチェック
    for (long long i=0; i+s1_len<=s2_len; i++) {
        if (s1h == s2h) return i;  // s2のi文字目からのs1_len文字が一致
        if (i+s1_len < s2_len) s2h = s2h * B + s2[i+s1_len] - s2[i]*t;
    }

    return -1;
 }


/***文字列s1の末尾とs2の先頭を何文字重ねることができるか？
 * Returns:
 *  重なっている文字数を返す。
 *  重なっていなかった場合、0を返す
 ***/
long long overlap(string s1, string s2) {
    long long s1_len = s1.length();
    long long s2_len = s2.length();
    long long ans = 0;
    unsigned long long s1h = 0, s2h = 0;  // ハッシュ値
    unsigned long long t = 1;

    for (long long i=1; i<=min(s1_len, s2_len); i++) {
        s1h = s1h + s1[s1_len-i]*t;  // s1の末尾i文字のハッシュ値
        s2h = s2h * B + s2[i-1];     // s2の先頭i文字のハッシュ値
        if (s1h == s2h) ans = i;
        t *= B;
    }

    return ans;
}


void solve() {
    string S; cin >> S;
    ll M; cin >> M;
    vector<string> C(M);
    for(ll i=0; i<M; i++) {
        cin >> C[i];
    }

    // ローリングハッシュで文字列検索する
    ll ans = 0;
    for(ll i=0; i<M; i++) {
        ll start = 0; // Sの開始位置
        while(1) {
            ll idx = contain(C[i], S.substr(start));
            if (idx == -1) break;
            ans++;
            start += idx + 1;
            if (start >= (ll)S.size()) break;
        }
    }
    cout << ans << endl;
}


int main() {
    solve();
    return 0;
}
0