結果

問題 No.430 文字列検索
ユーザー ありあり
提出日時 2023-04-01 16:32:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,062 ms / 2,000 ms
コード長 2,682 bytes
コンパイル時間 990 ms
コンパイル使用メモリ 106,372 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-24 18:16:35
合計ジャッジ時間 12,474 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1,059 ms
4,348 KB
testcase_02 AC 1,058 ms
4,348 KB
testcase_03 AC 1,058 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 8 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 1,060 ms
4,348 KB
testcase_12 AC 1,062 ms
4,348 KB
testcase_13 AC 1,058 ms
4,348 KB
testcase_14 AC 1,058 ms
4,348 KB
testcase_15 AC 1,060 ms
4,348 KB
testcase_16 AC 1,059 ms
4,348 KB
testcase_17 AC 1,062 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cassert>
#include <cmath>
#include <bitset>
#include <cctype>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
struct RollingHash {
private:
  using ull = unsigned long long;
  static const ull _mod = 0x1fffffffffffffff;
  static ull _base;
  vector<ull> _hashed, _power;
 
  inline ull _mul(ull a, ull b) const {
    ull au = a >> 31;
    ull ad = a & ((1UL << 31) - 1);
    ull bu = b >> 31;
    ull bd = b & ((1UL << 31) - 1);
    ull mid = ad * bu + au * bd;
    ull midu = mid >> 30;
    ull midd = mid & ((1UL << 30) - 1);
    ull ans = au * bu * 2 + midu + (midd << 31) + ad * bd;
    
    ans = (ans >> 61) + (ans & _mod);
    if (ans >= _mod) ans -= _mod;
    return ans;
  }
public:
  RollingHash(const string &s) {
    ll n = s.size();
    _hashed.assign(n + 1, 0);
    _power.assign(n + 1, 0);
    _power[0] = 1;
    for(ll i = 0; i < n; i++) {
        _power[i + 1] = _mul(_power[i], _base);
        _hashed[i + 1] = _mul(_hashed[i], _base) + s[i];
        if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
    }
  }
  
  ull get(ll l, ll r) const {
    ull ret = _hashed[r] + _mod - _mul(_hashed[l], _power[r - l]);
    if(ret >= _mod) ret -= _mod;
    return ret;
  }
  
  ull connect(ull h1, ull h2, ll h2len) const {
    ull ret = _mul(h1, _power[h2len]) + h2;
    if(ret >= _mod) ret -= _mod;
    return ret;
  }
  
  void connect(const string &s) {
    ll n = _hashed.size() - 1, m = s.size();
    _hashed.resize(n + m + 1);
    _power.resize(n + m + 1);
    for(ll i = n; i < n + m; i++) {
      _power[i + 1] = _mul(_power[i], _base);
      _hashed[i + 1] = _mul(_hashed[i], _base) + s[i - n];
      if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
    }
  }
  
  ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) const {
    ll len = min(r1 - l1, r2 - l2);
    ll low = -1, high = len + 1;
    while(high - low > 1) {
      ll mid = (low + high) / 2;
      if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return low;
  }
};
mt19937_64 mt{(unsigned int)time(NULL)};
RollingHash::ull RollingHash::_base = mt() % RollingHash::_mod;

int main() {
  string s;
  cin >> s;
  RollingHash sh(s);
  int m;
  cin >> m;
  int ans = 0;
  for (int _ = 0; _ < m; _++) {
    string c;
    cin >> c;
    RollingHash ch(c);
    for (int i = 0; i+c.size() <= s.size(); i++)
      if (sh.get(i, i+c.size()) == ch.get(0, c.size()))
        ans++;
  }
  cout << ans << endl;
  return 0;
}
0