結果
問題 | No.430 文字列検索 |
ユーザー | tatananonano |
提出日時 | 2023-01-09 18:00:41 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 353 ms / 2,000 ms |
コード長 | 5,762 bytes |
コンパイル時間 | 6,728 ms |
コンパイル使用メモリ | 286,912 KB |
実行使用メモリ | 26,752 KB |
最終ジャッジ日時 | 2024-08-15 16:40:30 |
合計ジャッジ時間 | 8,431 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 342 ms
26,752 KB |
testcase_03 | AC | 8 ms
6,940 KB |
testcase_04 | AC | 10 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 3 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 353 ms
26,624 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 15 ms
6,940 KB |
testcase_12 | AC | 62 ms
7,680 KB |
testcase_13 | AC | 63 ms
7,808 KB |
testcase_14 | AC | 63 ms
7,808 KB |
testcase_15 | AC | 48 ms
6,944 KB |
testcase_16 | AC | 37 ms
6,940 KB |
testcase_17 | AC | 11 ms
6,944 KB |
testcase_18 | AC | 11 ms
6,944 KB |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <deque> #include <list> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <set> #include <map> #include <ctime> #include <stack> #include <functional> #include <cstdio> #include <string> #include <iostream> #include <limits> #include <stdexcept> #include <numeric> #include <fstream> #include <chrono> #include <utility> #include <cassert> #include <random> #include <time.h> using namespace std; // /* #include <atcoder/all> using namespace atcoder; //using mint =modint998244353; //using mint =modint1000000009; using mint =modint1000000007; #define ip(x) is_prime_constexpr(x) // */ typedef long long ll; using ull = unsigned long long; typedef long double LD; typedef double D; typedef pair<ll,ll> P; typedef map<ll,ll> M; #define rep(i,n) for(auto i=0;i<n;i++) #define rrep(i,n) for(ll i=1;i<n;i++) #define jep(i, a, n)for (ll i =(ll)a; i<(ll)n;++i) #define drep2(i, m, n) for (int i = (n)-1; i >= (m); --i) #define drep(i, n) drep2(i,0,n) #define fore(i,a) for(const auto &i:a) #define all(x) (x).begin(),(x).end() #define pb push_back #define lb lower_bound #define ub upper_bound #define uni(x) sort(all(x));x.erase(unique(all(x)),x.end()) #define TFU(s) transform(all(s),begin(s),::toupper);//大文字にする #define TFL(s) transform(all(s),begin(s),::tolower);//小文字にする #define replace(s,a,A) replace(s,'a','A')//str(s)のaをAにする #define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする #define PQ priority_queue #define PQD PQ<P,vector<P>,greater<P>>//小さい順に吐く #define PQS PQ<ll,vec,greater<ll>>//小さい順に吐く #define fi first #define se second #define bit(n,k) ((n>>k)&1LL) #define printd(n,x) cout<<fixed<<setprecision(n)<<x<<endl #define cinv(a,n); rep(i,n){cin>>a[i];} #define popcount(n) __builtin_popcountll(n) template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;} template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;} typedef vector<ll> vec; typedef vector<vec> mat; //const ll mod = 1000000009; //const ll mod = 998244353; const ll mod = 1000000007; const auto INF = (1LL<<(60)); ll modpow(ll a,ll n,ll mod){if(mod==1)return 0;ll ret=1;ll p=a%mod;while(n){if(n&1)ret=ret*p%mod;p=p*p%mod;n>>=1;}return ret; } M factor(ll n) {M ret;for(ll i=2;i*i<=n;i++){while(n%i==0){ret[i]++;n /= i;}}if(n != 1){ret[n]=1;}return ret;}//素因数分解 vec divisor(ll n){vec K;for(ll i=1;i*i<=n;i++){if(n%i==0){K.pb(i);if(i*i!=n)K.pb(n/i);}}sort(all(K));return K;}//約数列挙 void tatananonano() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout<< fixed << setprecision(10); } #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;IN(__VA_ARGS__) template <class T> void scan(T &a) { cin >> a; } void IN() {} template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {scan(head);IN(tail...);} class RollingHash { static const uint64_t mod = (1ull << 61ull) - 1; vector<uint64_t> power; const uint64_t base; //1以上mod - 1以下のランダムなbaseを生成 static inline uint64_t generate_base() { mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<uint64_t> rand((uint64_t)1,(uint64_t)mod - 1); return rand(engine); } //足し算 static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= mod) a -= mod; return a; } //掛け算(__uint128_tを使用) static inline uint64_t mul(uint64_t a, uint64_t b) { __uint128_t c = (__uint128_t) a * b; return add(c >> 61,c & mod); } inline void expand(size_t sz) { if(power.size() < sz + 1) { int pre_sz = (int)power.size(); power.resize(sz + 1); for(int i = pre_sz - 1;i < sz;i++) { power.at(i + 1) = mul(power.at(i),base); } } } public: explicit RollingHash(uint64_t base = generate_base()) : base(base),power{1} {} //文字列Sのハッシュを返す vector<uint64_t> build(string S) { vector<uint64_t> hash(S.size() + 1); for (int i = 0; i < S.size(); i++) { hash.at(i + 1) = add(mul(hash.at(i),base),S.at(i)); } return hash; } //hashの[l,r)のハッシュ値を返す uint64_t query(vector<uint64_t> &hash,int l,int r) { expand(r - l); return add(hash.at(r),mod - mul(hash.at(l),power.at(r - l))); } //ハッシュ値h1と長さh2lenのハッシュ値h2を結合 uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) { expand(h2len); return add(mul(h1, power.at(h2len)), h2); } //hash1の区間[l1,r1)とhash2の区間[l2,r2)のlcp(最長共通接頭辞)の長さを返す ll lcp(vector<uint64_t> &hash1,ll l1,ll r1,vector<uint64_t> &hash2,ll l2,ll r2) { ll len = min(r1 - l1,r2 - l2); ll ok = 0; ll ng = len + 1; ll mid; while(ng - ok > 1) { mid = (ok + ng) / 2; if(query(hash1,l1,l1 + mid) == query(hash2,l2,l2 + mid)) ok = mid; else ng = mid; } return ok; } }; /* =======================[使い方(主要)]========================== RollingHash rh; auto v=rh.build(strの何か); rh.query(v,a,b) -> [a,b)のhash値 //S[l,r)が回文なのか判定したい string s; string t=s; reverse(all(t)); RollingHash rh; auto rolls=rh.build(s); auto rollt=rh.build(t); rep(qi,q){ ll l,r; cin>>l>>r; l--; cout << (rh.query(rolls,l,r)==rh.query(rollt,n-r,n-l) ? "Yes" : "No") <<endl; } } */ int main(){ tatananonano(); STR(s); LL(m); RollingHash rh; auto ros=rh.build(s); map<ll,ll> mp; rrep(i,min(ll(11),ll(s.size()+1))){ rep(j,s.size()-i+1){ mp[rh.query(ros,j,j+i)]++; } } ll ans=0; rep(qi,m){ STR(c); auto now=rh.build(c); ll key=rh.query(now,0,c.size()); ans+=mp[key]; } cout<<ans<<endl; }