結果

問題 No.430 文字列検索
ユーザー sekiya9311
提出日時 2016-10-04 13:21:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,658 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 110,344 KB
実行使用メモリ 11,684 KB
最終ジャッジ日時 2024-11-10 00:08:58
合計ジャッジ時間 4,346 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--)
#define PI acos(-1.0)
#define DEBUG(C) cerr << C << endl;
#define VI vector <int>
#define VII vector <VI>
#define VL vector <LL>
#define VLL vector <VL>
#define VD vector <double>
#define VDD vector <VD>
#define PII pair <int, int>
#define PDD pair <double, double>
#define PLL pair <LL, LL>
#define VPII vector <PII>
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EB emplace_back
#define FORE(a, b) for (auto &&a:b)
#define FIND(s, n) (s.find(n) != s.end())
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
class RollingHash {
private:
    const LL mods[2] = {(LL)(1e9 + 7), (LL)(1e9 + 9)};
    vector <long long> hs[2], pow[2];
    vector <long long> x; //基数
    int len;
    string S;
public:
    //文字列, 基数1, 基数2
    RollingHash(const string& str, long long num1, long long num2) {
        x.resize(2);
        x[0] = num1; x[1] = num2;
        S = str;
        init(S);
    }
    void init(const string& str) {
        len = str.length();
        for (int i = 0; i < 2; i++) {
            hs[i].resize(len + 5);
            pow[i].resize(len + 5);
            pow[i][0] = 1;
            for (int j = 0; j < len; j++) {
                pow[i][j + 1] = (pow[i][j] * x[i]) % mods[i];
            }
        }
        for (int i = 0; i < 2; i++) {
            for (int j  = 0; j < len; j++) {
                hs[i][j + 1] = (hs[i][j] + pow[i][j] * (long long)str[j]) % mods[i];
            }
        }
    }
    pair <long long, long long> makeHash(const string& str) {
        long long res[2];
        int slen = str.length();
        for (int i = 0; i < 2; i++) {
            res[i] = 0;
            for (int j = 0;j < slen; j++) {
                res[i] = (res[i] + pow[i][j] * (long long)str[j]) % mods[i];
            }
        }
        return make_pair(res[0], res[1]);
    }
    pair <vector <long long>, vector <long long>> getHash() {
        return make_pair(hs[0], hs[1]);
    }
    //引数の文字列と一致する場所
    //引数の文字列と一致する数
    int matchNum(const string& str) {
        auto p = makeHash(str);
        int res = 0;
        int slen = str.length();
        for (int i = slen; i < len + 1; i++) {
            LL hs1 = (hs[0][i] - hs[0][i - slen] + mods[0]) % mods[0];
            LL hs2 = (hs[1][i] - hs[1][i - slen] + mods[1]) % mods[1];
            res += (p == MP(hs1, hs2));
            p.first = p.first * x[0] % mods[0];
            p.second = p.second * x[1] % mods[1];
        }
        return res;
    }
};
int main(void) {
    string S;
    cin >> S;
    RollingHash r(S, 1234567, 8901234);
    int M; cin >> M;
    int ans = 0;
    REP(i, M) {
        string s;
        cin >> s;
        ans += r.matchNum(s);
    }
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0