結果
問題 | No.430 文字列検索 |
ユーザー | takuwwwo |
提出日時 | 2019-11-15 22:55:31 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 2,942 bytes |
コンパイル時間 | 1,279 ms |
コンパイル使用メモリ | 113,392 KB |
実行使用メモリ | 26,240 KB |
最終ジャッジ日時 | 2024-11-10 00:36:52 |
合計ジャッジ時間 | 2,324 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 195 ms
26,240 KB |
testcase_02 | AC | 8 ms
5,248 KB |
testcase_03 | AC | 8 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 186 ms
26,240 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 13 ms
5,632 KB |
testcase_11 | AC | 69 ms
7,424 KB |
testcase_12 | AC | 67 ms
7,424 KB |
testcase_13 | AC | 70 ms
7,296 KB |
testcase_14 | AC | 54 ms
5,760 KB |
testcase_15 | AC | 42 ms
5,248 KB |
testcase_16 | AC | 13 ms
5,248 KB |
testcase_17 | AC | 10 ms
5,248 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <unordered_map> #include <queue> #include <set> #include <algorithm> #include <string> #include <math.h> #include <limits.h> #include <stack> #include <complex> #include <stdlib.h> #include <stdio.h> #include <functional> #include <cfloat> #include <math.h> #include <numeric> #include <string.h> #include <sys/time.h> #include <random> #define fs first #define sc second using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef pair<P, ll> T; const ll mod = 1000000007; ll fact[200200]; ll invfact[200200]; inline ll take_mod(ll a){ return (a % mod + mod) % mod; } inline ll add(ll a, ll b){ return take_mod(a+b); } inline ll sub(ll a, ll b){ return take_mod(a-b); } inline ll mul(ll a, ll b){ return take_mod(a * b); } inline ll pow(ll x, ll n){ ll res = 1LL; while(n > 0){ if(n & 1) res = mul(res, x); x = mul(x, x); n >>= 1; } return res; } ll mod_inv(ll x){ return pow(x, mod-2); } // nは上限 void make_fact(ll n){ fact[0] = 1; ll res = 1; for(int i = 1; i <= n; i++){ fact[i] = res; res = mul(res, i+1); } } // nは上限 void make_invfact(ll n){ invfact[0] = 1; invfact[n] = mod_inv(fact[n]); for(int i = n-1; i >= 1; i--){ invfact[i] = mul(invfact[i + 1], i + 1); } } ll perm(ll n, ll k){ return mul(fact[n], invfact[n-k]); } ll comb(ll n, ll k){ return mul(mul(fact[n], invfact[n-k]), invfact[k]); } class RollingHash{ public: map<ll, int> hash; RollingHash(){ } void add(ll hash_num){ if(hash.find(hash_num) == hash.end()){ hash[hash_num] = 1; } else { hash[hash_num] += 1; } } int search(ll hash_num){ if(hash.find(hash_num) == hash.end()){ return 0; } else{ return hash[hash_num]; } } }; int main(){ RollingHash rh = RollingHash(); ll powList[11]; powList[0] = 1; for(int i = 1; i < 11; i++){ powList[i] = (ll)(27) * powList[i-1]; } string s; cin >> s; for(int i = 1; i <= 10; i++){ ll hashNum = 0; for(int j = 0; j < s.length(); j++){ if(j - i >= 0){ hashNum -= (s[j-i] - 'A' + 1) * powList[i-1]; } hashNum *= 27; hashNum += s[j] - 'A' + 1; if(j - i + 1 >= 0){ // cout << hashNum << endl; rh.add(hashNum); } } } int M; cin >> M; int res = 0; for(int i = 0; i < M; i++){ string c; cin >> c; ll hashNum = 0; for(int j = 0; j < c.length(); j++){ hashNum *= 27; hashNum += c[j] - 'A' + 1; } res += rh.search(hashNum); // cout << res << endl; } cout << res << endl; return 0; }