結果

問題 No.430 文字列検索
ユーザー utouto97
提出日時 2019-08-14 16:51:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 421 ms / 2,000 ms
コード長 1,777 bytes
コンパイル時間 1,349 ms
コンパイル使用メモリ 176,624 KB
実行使用メモリ 45,184 KB
最終ジャッジ日時 2024-11-10 00:28:46
合計ジャッジ時間 3,467 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
  }*/

class RollingHash{
  public:
    const int K = 2;
    vector<long long> M, B;
    vector<vector<long long>> hash, p;

    RollingHash(const string &s, vector<long long> b={107,311})
      : M({1000000007, 1000000009}), B(b), hash(K), p(K){
        int n = s.size();
        for(int i = 0; i < K; i++){
          hash[i].assign(n+1, 0); 
          p[i].assign(n+1, 1);
          for(int j = 0; j < n; j++){
            hash[i][j+1] = (hash[i][j]*B[i] + s[j])%M[i];
            p[i][j+1] = p[i][j]*B[i]%M[i];
          }
        }
      }

    vector<long long> find(int l, int r){
      vector<long long> res(K);
      for(int i = 0; i < K; i++){
        long long tmp = hash[i][r] + M[i] - hash[i][l]*p[i][r-l]%M[i];
        res[i] = tmp >= M[i] ? tmp-M[i] : tmp;
      }
      return res;
    }
};

signed main(){
  srand((unsigned)time(NULL));

  string s;
  cin >> s;

  long long B1 = rand()%10000+100000;
  long long B2 = rand()%10000+500000;

  RollingHash rh(s, {B1, B2});
  map<vector<int>, int> cnt;
  rep(i, 0, s.size()) rep(j, 1, 11){
    if(i+j <= s.size()){
      cnt[rh.find(i, i+j)]++;
    }
  }

  int m;
  cin >> m;

  int ans = 0;
  rep(i, 0, m){
    string c;
    cin >> c;

    RollingHash rh2(c, {B1, B2});
    ans += cnt[rh2.find(0, c.size())];
  }

  cout << ans << endl;

  return 0;
}
0