結果

問題 No.430 文字列検索
コンテスト
ユーザー yukim0359
提出日時 2024-06-23 01:03:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,122 bytes
コンパイル時間 1,497 ms
コンパイル使用メモリ 176,212 KB
実行使用メモリ 49,280 KB
最終ジャッジ日時 2024-11-10 01:11:50
合計ジャッジ時間 4,423 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

//  https://yukicoder.me/problems/no/430
//  ハッシュは文字に数字0を対応させると衝突が起こる(AとAAが同じハッシュになる)
//  なので必ず1から対応させる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep0(i,n) for(int i=0; i<n; ++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)

ll powpow(ll x, ll n){
  if(n==0) return 1;
  ll tmp = powpow(x, n/2);
  if(n % 2 == 1) return (tmp * tmp* x);
  else return (tmp * tmp);
}

int base = 27;  // 26+1

ll powpowm(ll x, ll n, ll mod){
  if(n==0) return 1;
  ll tmp = powpowm(x, n/2, mod);
  if(n % 2 == 1) return (((tmp * tmp) % mod) * x) % mod;
  else return (tmp * tmp) % mod;
}

// ハッシュを計算
ll CalcHash(string pattern, ll mod){
  int p_len = pattern.length();
  ll p_hash = 0;
  rep0(i, p_len){
    p_hash += powpowm(base, p_len-1-i, mod) * (ll)(pattern[i] + 1 - 'A');
    p_hash %= mod;
  }
  return p_hash;
}

// 部分文字列のハッシュをすべて管理するmapを作る
void MakeRollingHashMap(string text, ll mod, map<ll, int> &mp){
  int t_len = text.length();
  rep1(len, min(10, t_len)){
    ll t_hash = 0;
    rep0(i, len){
      t_hash += powpowm(base, len - 1 - i, mod) * (ll)(text[i] + 1 - 'A');
      t_hash %= mod;
    }
    mp[t_hash] += 1;

    // 先頭文字でforを回してt_hashを更新していく
    for(int i=1; i<=t_len-len; ++i){
      ll new_hash = (base * t_hash) % mod;
      new_hash = (new_hash - powpowm(base, len, mod) * (text[i-1] + 1 - 'A') + mod) % mod;
      new_hash += (text[i + len - 1] + 1 - 'A');
      new_hash %= mod;
      t_hash = new_hash;
      mp[t_hash] += 1;
    }
  }
}

int main(){
  ll mod1 = 1000000007;
  ll mod2 = 998244353;
  string S;
  cin >> S;
  int M;
  cin >> M;

  map<ll,int> mp1;
  MakeRollingHashMap(S, mod1, mp1);
  map<ll,int> mp2;
  MakeRollingHashMap(S, mod2, mp2);

  int ans = 0;
  rep1(i, M){
    string C;
    cin >> C;
    ll hsh1 = CalcHash(C, mod1);
    ll hsh2 = CalcHash(C, mod2);
    if(mp1.count(hsh1) && mp2.count(hsh2)) ans += mp1[hsh1];
  }
  cout << ans << endl;
}
0