結果

問題 No.430 文字列検索
ユーザー utouto97utouto97
提出日時 2019-08-14 16:51:25
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 421 ms
45,184 KB
testcase_02 AC 36 ms
5,376 KB
testcase_03 AC 36 ms
5,376 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 383 ms
44,672 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 21 ms
7,680 KB
testcase_11 AC 128 ms
11,648 KB
testcase_12 AC 133 ms
11,904 KB
testcase_13 AC 129 ms
11,776 KB
testcase_14 AC 105 ms
9,088 KB
testcase_15 AC 86 ms
7,680 KB
testcase_16 AC 44 ms
5,632 KB
testcase_17 AC 39 ms
5,376 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