結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl
#define dump(x)  cerr << #x << " => " << (x) << endl
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w)
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double EPS = 1e-10;
constexpr long MOD = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL,LL> pr;
typedef vector<bool> VB;
typedef vector<pr> VP;
typedef priority_queue<pr,vector<pr>,greater<pr>> pq;


// ローリングハッシュのライブラリ
template<unsigned long long mod1,unsigned long long mod2>
class RollingHash {
private:
    typedef unsigned long long ULL;
    typedef pair<ULL,ULL> PULL;
    int len;
    vector<ULL> power1; 
    vector<ULL> power2;
public:
    string S;
    // hashed[k] : 先頭k文字のhash値
    vector<ULL> hashed1;
    vector<ULL> hashed2;
    // s : 検索対象の文字列
    RollingHash(const string &s,ULL base1 = 10007LL,ULL base2 = 10009LL) : 
        S(s),len(s.size()),power1(len+1,1),power2(len+1,1),hashed1(len+1,0),hashed2(len+1,0) {
        // O(N)
        for (int i = 0;i < len ;i++) {
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
            hashed1[i+1] = ((hashed1[i] * base1) + s[i]) % mod1;
            hashed2[i+1] = ((hashed2[i] * base2) + s[i]) % mod2;
        }
    }

    // [l,r) のハッシュ値を求める.
    PULL getHash(int l,int r) {
        // 負の数にならないようにmodを取ること.
        ULL p1 = ((hashed1[r]+mod1) - ((hashed1[l] * power1[r-l])%mod1))%mod1;
        ULL p2 = ((hashed2[r]+mod2) - ((hashed2[l] * power2[r-l])%mod2))%mod2;
        return make_pair(p1,p2);
    }
    // []
    PULL connect(PULL h1,PULL h2,int h2len) {
        return make_pair(((h1.first*power1[h2len]) + h2.first)%mod1,((h1.second*power2[h2len]) + h2.second)%mod2);
    }

    // 区間[l1,r1) と bの区間[l2,r2) の最長共通接頭辞の長さを求める. O(log N)
    int LCP(const RollingHash<mod1,mod2> &b,int l1 ,int r1 ,int l2 ,int r2 ) {
        int sz = min(r1 - l1,r2 - l2);
        int low = (-1),high = sz + 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (getHash(l1,l1+mid) == b.getHash(l2,l2+mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};
typedef RollingHash<999999937LL,1000000009LL> RH;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long M;
    string S,c;
    cin >> S;
    cin >> M;
    RH rhs(S);
    int ls = S.size();
    LL cnt = 0;
    REP(i,M) {
        cin >> c;
        int lc = c.size();
        RH rhc(c);
        auto hash = rhc.getHash(0,c.size());
        REP(j,ls - (int)c.size() + 1) {
            if (hash == rhs.getHash(j,j+lc)) cnt++;
        }
    }
    cout << cnt << endl;
}
0