#341198 (C++11) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	omochana2
提出日時	2019-04-20 19:27:20
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	296 ms / 2,000 ms
コード長	5,661 bytes
コンパイル時間	1,289 ms
コンパイル使用メモリ	172,788 KB
実行使用メモリ	26,624 KB
最終ジャッジ日時	2024-11-10 00:23:40
合計ジャッジ時間	2,833 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	282 ms 26,624 KB
testcase_02	AC	19 ms 6,820 KB
testcase_03	AC	19 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	1 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	296 ms 26,496 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	15 ms 6,816 KB
testcase_11	AC	72 ms 7,552 KB
testcase_12	AC	72 ms 7,936 KB
testcase_13	AC	72 ms 7,424 KB
testcase_14	AC	56 ms 6,820 KB
testcase_15	AC	45 ms 6,820 KB
testcase_16	AC	23 ms 6,816 KB
testcase_17	AC	22 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

template<int mod>
struct mint{
  int x;
  mint() : x(0) {}
  mint(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  mint &operator+=(const mint &p) { if((x += p.x) >= mod) x -= mod; return *this; }
  mint &operator-=(const mint &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; }
  mint &operator*=(const mint &p) { x = (int) (1LL * x * p.x % mod); return *this; }
  mint &operator/=(const mint &p) { *this *= p.inverse(); return *this; }
  mint &operator^=(ll n) {
    int y = x; x = 1;
    while(n > 0) {
      if(n & 1) x = 1LL * x * y % mod; y = 1LL * y * y % mod; n /= 2; }
    return *this; }
  mint operator-() const { return mint(-x); }
  mint operator+(const mint &p) const { return mint(*this) += p; }
  mint operator-(const mint &p) const { return mint(*this) -= p; }
  mint operator*(const mint &p) const { return mint(*this) *= p; }
  mint operator/(const mint &p) const { return mint(*this) /= p; }
  mint operator^(const ll n) const { return mint(*this) ^= n; }
  bool operator==(const mint &p) const { return x == p.x; }
  bool operator!=(const mint &p) const { return x != p.x; }
  mint inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
    return mint(u); }
  friend ostream &operator<<(ostream &os, const mint<mod> &p) { return os << p.x; }
  friend istream &operator>>(istream &is, mint< mod > &a) { 
	  ll t; is >> t; a = mint<mod>(t); return (is); }
};

struct rhash { //don't forget to base_init()!!!!!
	mint<1000000007> v1;
	mint<1000000009> v2;
	rhash() : v1(0), v2(0) {}
	rhash(ll a) : v1(a), v2(a) {}
	rhash(ll a, ll b) : v1(a), v2(b) {}
	rhash &operator+=(const rhash &hs) { v1 += hs.v1; v2 += hs.v2; return *this; }
	rhash &operator-=(const rhash &hs) { v1 -= hs.v1; v2 -= hs.v2; return *this; }
	rhash &operator*=(const rhash &hs) { v1 *= hs.v1; v2 *= hs.v2; return *this; }
	rhash &operator/=(const rhash &hs) { v1 /= hs.v1; v2 /= hs.v2; return *this; }
	rhash &operator^=(ll n) { v1 ^= n; v2 ^= n; return *this; }
	rhash operator-() const { rhash hs; hs.v1 = -v1; hs.v2 = -v2; return hs; }
	rhash operator+(const rhash& hs) const { return rhash(*this) += hs; }
	rhash operator-(const rhash& hs) const { return rhash(*this) -= hs; }
	rhash operator*(const rhash& hs) const { return rhash(*this) *= hs; }
	rhash operator/(const rhash& hs) const { return rhash(*this) /= hs; }
	rhash operator^(ll n) const { return rhash(*this) ^= n; }
	bool operator<(const rhash &hs) const { return pi(v1.x, v2.x) < pi(hs.v1.x, hs.v2.x); }
	bool operator==(const rhash& hs) { return v1 == hs.v1 && v2 == hs.v2; }
	bool operator!=(const rhash& hs) { return v1 != hs.v1 || v2 != hs.v2; }
	friend ostream &operator<<(ostream &os, const rhash &hs) { return os << pi(hs.v1.x, hs.v2.x); }
};

rhash base;

void base_init() {
	int v1 = uniform_int_distribution<int>(0, 1000000007 - 1)(rng);
	int v2 = uniform_int_distribution<int>(0, 1000000009 - 1)(rng);
	base = rhash(v1, v2);
}

int N, M;
string S;

map<pair<rhash, int>, int> G;

void solve() {
	base_init();
	cin >> S;
	N = sz(S);
	S += '$';
	rep(l, 1, 10 + 1) {
		rhash hs = 0;
		if(l > N) continue;
		rep(i, 0, l) {
			hs *= base;
			hs += (S[i] - 'A');
		}
		rep(i, 0, N - l + 1) {
			G[make_pair(hs, l)]++;
			hs -= rhash(S[i] - 'A') * (base ^ (l - 1));
			hs *= base;
			hs += rhash(S[i + l] - 'A');
		}
	}
	cin >> M;
	ll sum = 0;
	while(M--) {
		string str; cin >> str;
		rhash hs = 0;
		rep(i, 0, sz(str)) {
			hs *= base;
			hs += (str[i] - 'A');
		}
		sum += G[make_pair(hs, sz(str))];
	}
	cout << sum << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

yukicoder

結果

テストケース

ソースコード