結果

問題 No.430 文字列検索
ユーザー utouto97utouto97
提出日時 2019-08-14 16:51:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 647 ms / 2,000 ms
コード長 1,777 bytes
コンパイル時間 2,627 ms
コンパイル使用メモリ 176,080 KB
実行使用メモリ 45,296 KB
最終ジャッジ日時 2023-10-19 18:10:40
合計ジャッジ時間 5,274 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 647 ms
45,296 KB
testcase_02 AC 41 ms
5,444 KB
testcase_03 AC 42 ms
5,444 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 620 ms
44,780 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 28 ms
7,832 KB
testcase_11 AC 183 ms
11,780 KB
testcase_12 AC 182 ms
12,044 KB
testcase_13 AC 184 ms
12,044 KB
testcase_14 AC 136 ms
9,140 KB
testcase_15 AC 108 ms
7,556 KB
testcase_16 AC 50 ms
5,708 KB
testcase_17 AC 46 ms
5,444 KB
権限があれば一括ダウンロードができます

ソースコード

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