#831750 (C++23(draft)) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	tatananonano
提出日時	2023-01-09 18:01:30
言語	C++23(draft) (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	224 ms / 2,000 ms
コード長	5,772 bytes
コンパイル時間	6,616 ms
コンパイル使用メモリ	289,508 KB
実行使用メモリ	22,852 KB
最終ジャッジ日時	2023-08-22 19:43:01
合計ジャッジ時間	8,124 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	217 ms 22,852 KB
testcase_02	AC	10 ms 4,376 KB
testcase_03	AC	10 ms 4,376 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	224 ms 22,800 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	8 ms 4,608 KB
testcase_11	AC	29 ms 6,260 KB
testcase_12	AC	28 ms 6,428 KB
testcase_13	AC	29 ms 6,336 KB
testcase_14	AC	23 ms 5,260 KB
testcase_15	AC	20 ms 4,796 KB
testcase_16	AC	12 ms 4,376 KB
testcase_17	AC	11 ms 4,380 KB

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

ソースコード

raw source code

#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);
unordered_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;
}

yukicoder

結果

テストケース

ソースコード