結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2024-08-25 12:27:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 10,374 bytes |
コンパイル時間 | 1,375 ms |
コンパイル使用メモリ | 131,836 KB |
最終ジャッジ日時 | 2025-02-24 00:43:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include<iostream>#include<string>#include<queue>#include<vector>#include<cassert>#include<random>#include<set>#include<map>#include<cassert>#include<unordered_map>#include<bitset>#include<numeric>#include<algorithm>using namespace std;typedef long long ll;const int inf=1<<30;const ll INF=1LL<<62;typedef pair<int,ll> P;typedef pair<int,P> PP;const ll MOD=998244353;// SA-IS (O(N))template<class Str> struct SuffixArray {// dataStr str;//sa[0]は空文字になっていることに注意vector<int> sa, rsa, lcp;//勝手に代入されるint& operator [] (int i) {return sa[i];}// constructorSuffixArray(const Str& str_) : str(str_) {build_sa();}void init(const Str& str_) {str = str_;build_sa();}void build_sa() {int N = (int)str.size();vector<int> s;for (int i = 0; i < N; ++i) s.push_back(str[i] + 1);s.push_back(0);sa = sa_is(s);rsa.assign(N + 1, 0);for (int i = 0; i <= N; ++i) rsa[sa[i]] = i;calc_lcp(s);}// SA-IS// upper: # of charactersvector<int> sa_is(vector<int> &s, int upper = 256) {int N = (int)s.size();if (N == 0) return {};else if (N == 1) return {0};else if (N == 2) {if (s[0] < s[1]) return {0, 1};else return {1, 0};}vector<int> isa(N);vector<bool> ls(N, false);for (int i = N - 2; i >= 0; --i) {ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);}vector<int> sum_l(upper + 1, 0), sum_s(upper + 1, 0);for (int i = 0; i < N; ++i) {if (!ls[i]) ++sum_s[s[i]];else ++sum_l[s[i] + 1];}for (int i = 0; i <= upper; ++i) {sum_s[i] += sum_l[i];if (i < upper) sum_l[i + 1] += sum_s[i];}auto induce = [&](const vector<int> &lms) -> void {fill(isa.begin(), isa.end(), -1);vector<int> buf(upper + 1);copy(sum_s.begin(), sum_s.end(), buf.begin());for (auto d: lms) {if (d == N) continue;isa[buf[s[d]]++] = d;}copy(sum_l.begin(), sum_l.end(), buf.begin());isa[buf[s[N - 1]]++] = N - 1;for (int i = 0; i < N; ++i) {int v = isa[i];if (v >= 1 && !ls[v - 1]) {isa[buf[s[v - 1]]++] = v - 1;}}copy(sum_l.begin(), sum_l.end(), buf.begin());for (int i = N - 1; i >= 0; --i) {int v = isa[i];if (v >= 1 && ls[v - 1]) {isa[--buf[s[v - 1] + 1]] = v - 1;}}};vector<int> lms, lms_map(N + 1, -1);int M = 0;for (int i = 1; i < N; ++i) {if (!ls[i - 1] && ls[i]) {lms_map[i] = M++;}}lms.reserve(M);for (int i = 1; i < N; ++i) {if (!ls[i - 1] && ls[i]) {lms.push_back(i);}}induce(lms);if (M) {vector<int> lms2;lms2.reserve(isa.size());for (auto v: isa) {if (lms_map[v] != -1) lms2.push_back(v);}int rec_upper = 0;vector<int> rec_s(M);rec_s[lms_map[lms2[0]]] = 0;for (int i = 1; i < M; ++i) {int l = lms2[i - 1], r = lms2[i];int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N;int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N;bool same = true;if (nl - l != nr - r) same = false;else {while (l < nl) {if (s[l] != s[r]) break;++l, ++r;}if (l == N || s[l] != s[r]) same = false;}if (!same) ++rec_upper;rec_s[lms_map[lms2[i]]] = rec_upper;}auto rec_sa = sa_is(rec_s, rec_upper);vector<int> sorted_lms(M);for (int i = 0; i < M; ++i) {sorted_lms[i] = lms[rec_sa[i]];}induce(sorted_lms);}return isa;}// prepair lcpvector<int> calc_lcp(const vector<int> &s) {int N = (int)s.size();lcp.assign(N - 1, 0);int h = 0;for (int i = 0; i < N - 1; ++i) {int pi = sa[rsa[i] - 1];if (h > 0) --h;for (; pi + h < N && i + h < N; ++h) {if (s[pi + h] != s[i + h]) break;}lcp[rsa[i] - 1] = h;}return lcp;}};struct z_algorithm{std::string s;int len;std::vector<int> z_array;bool is_build;z_algorithm(const std::string& s_):s(s_),len(s_.size()),is_build(false){z_array=std::vector<int>(len);build();}~z_algorithm(){std::vector<int>().swap(z_array);}void build(){is_build = true;z_array[0]=len;int i=1;int j=0;while(i<len){while(i+j<len && s[i+j]==s[j])j++;//一致しなくなる or それ以上伸ばせない場合z_array[i]=j;if(j==0){i++;continue;}//j>0int k=1;while(k<j && k+z_array[k]<j){z_array[i+k]=z_array[k];k++;}i+=k;j-=k;}}int operator[](int idx){assert(0<=idx && idx<len);if(!is_build) build();return z_array[idx];}void print(){for(int i=0;i<len;i++){std::cout<<"z_array["<<i<<"]="<<z_array[i]<<std::endl;}}};struct Trie{struct Node{std::map<char,int> to;int cnt;bool is_end;Node():cnt(0),is_end(false){}};vector<Node> nodes;Trie():nodes(1){}void insert(const string &s){int now=0;for(char c:s){if(!nodes[now].to.count(c)){nodes[now].to[c]=nodes.size();nodes.emplace_back(Node());}now=nodes[now].to[c];}nodes[now].cnt++;nodes[now].is_end=true;}ll ans=0;int dfs(int v){int res=nodes[v].cnt;for(auto [c,nv]:nodes[v].to){res+=dfs(nv);}if(v>0)ans+=res*(res-1)/2;return res;}};class RollingHash{long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}public:std::vector<long long> h;std::vector<long long> powBase;int len;std::string str;long long mod;long long base;//RollingHash(const std::string& str,long long base_=1000000+7,long long mod_=1000000000+7):base(base_),mod(mod_){RollingHash(const std::string& str,long long base_=1000000+7,long long mod_=998244353):base(base_),mod(mod_){len=str.size();h = std::vector<long long>(len+1,0);powBase = std::vector<long long>(len+1,0);assert(gcd(base_,mod_)==1);h[0]=0;for(int i=1;i<=len;i++){h[i]=(h[i-1]*base%mod + (int)str[i-1])%mod;}powBase[0]=1;for(int i=1;i<=len;i++){powBase[i]=powBase[i-1]*base%mod;}}~RollingHash(){std::vector<long long>().swap(h);std::vector<long long>().swap(powBase);}//[0,idx]のハッシュ値を取得long long get_hash(int idx){assert(0<=idx && idx<len);return h[idx+1];}long long pow(int i){assert(0<=i && i<=len);return powBase[i];}//0-indexed [l,r)のハッシュを取り出すlong long get_hash(int l,int r){assert(0<=l && r<=len);assert(l<r);int len=r-l;//[l,r)//h[r]-h[l]return (h[r] - (powBase[len]*h[l])%mod + mod)%mod;}long long getBase()const{return base;}long long getMod()const{return mod;}std::string getString()const{return str;}//[l,r)にしたいstd::string getSubString(int l,int r)const{int len=r-l;return str.substr(l,len);}//[lからlen文字std::string getSubString(int l,unsigned int len)const{return str.substr(l,len);}};int main(){string S;cin>>S;// map<string,int> mp;// for(int i=0;i<S.size();i++){// for(int j=1;j+i<=min(static_cast<int>(S.size()),10);j++){// mp[S.substr(i,j)]++;// }// }int M;cin>>M;vector<string> C(M);for(int i=0;i<M;i++){cin>>C[i];}ll ans=0;/*//zアルゴリズムは厳しいfor(int i=0;i<M;i++){string tmp=C[i]+'$'+S;z_algorithm za(tmp);int len=C[i].size();int cnt=0;for(int j=len+1;j+len<=tmp.size();j++){if(za[j]>=len){cnt++;}}ans+=cnt;}cout<<ans<<endl;*//*//これでもACRollingHash rh(S);vector<map<ll,ll>> mp(11);for(int x=1;x<=10;x++){for(int i=0;i+x<=S.size();i++){ll hash=rh.get_hash(i,i+x);mp[x][hash]++;}}for(int i=0;i<M;i++){RollingHash rh2(C[i]);ans+=mp[C[i].size()][rh2.get_hash(0,C[i].size())];}cout<<ans<<endl;*/map<string,ll> mp;for(int i=0;i<S.size();i++){for(int j=1;j<=10 && i+j<=S.size();j++){mp[S.substr(i,j)]++;}}for(int i=0;i<M;i++){ans+=mp[C[i]];}cout<<ans<<endl;}