This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2644 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../string/suffixarray.cpp" #include "../../segtree/basic/ushi.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); string s; int m; cin>>s>>m; SuffixArray sa(s); using P = pair<int, int>; auto f=[](P a,P b){ return P(max(a.first,b.first), min(a.second,b.second)); }; int n=s.size()+1; SegmentTree<P> seg(f,P(-1,n+1)); vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(sa[i],sa[i]); seg.build(vp); for(int i=0;i<m;i++){ string x,y;cin>>x>>y; int lx=sa.lower_bound(x); int rx=sa.upper_bound(x); int ly=sa.lower_bound(y); int ry=sa.upper_bound(y); int ans; if(rx-lx<=0||ry-ly<=0) ans=0; else{ int a=seg.query(ly,ry).first; int b=seg.query(lx,rx).second; if(b+(int)x.size()>a+(int)y.size()) ans=0; else ans=a-b+y.size(); } cout<<ans<<"\n"; } cout<<flush; return 0; }
#line 1 "test/aoj/2644.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2644 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "string/suffixarray.cpp" #line 3 "string/suffixarray.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename Seq = string> struct SuffixArray{ const Seq s; vector<int> sa,rev; SuffixArray(const Seq &s_):s(s_){ int n=s.size(); auto cmp=[&](int a,int b){ if(a==b) return false; if(a==n) return true; if(b==n) return false; if(s[a]==s[b]) return a>b; return s[a]<s[b]; }; sa.resize(n+1); iota(sa.begin(),sa.end(),0); sort(sa.begin(),sa.end(),cmp); vector<int> rs(n+1); { Seq t(s); sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); for(int i=0;i<n;i++) rs[i]=std::lower_bound(t.begin(),t.end(),s[i])-t.begin(); rs[n]=0; } for(int len=1;len<=n;len*=2){ vector<int> cs(n+1); for(int i=0;i<=n;i++){ cs[sa[i]]=i; if(i==0) continue; if(rs[sa[i-1]]!=rs[sa[i]]) continue; if(sa[i-1]+len>=n) continue; if(rs[sa[i-1]+len/2]!=rs[sa[i]+len/2]) continue; cs[sa[i]]=cs[sa[i-1]]; } vector<int> cnt(n+1); iota(cnt.begin(),cnt.end(),0); copy(sa.begin(),sa.end(),rs.begin()); for(int i=0;i<=n;i++){ int s1=rs[i]-len; if(s1>=0) sa[cnt[cs[s1]]++]=s1; } cs.swap(rs); } rev.resize(n+1); for(int i=0;i<=n;i++) rev[sa[i]]=i; } int operator[](int i) const{return sa[i];} bool lt_substr(const Seq &t,int si,int ti){ int sn=s.size(),tn=t.size(); while(si<sn and ti<tn){ if(s[si]<t[ti]) return 1; if(s[si]>t[ti]) return 0; si++;ti++; } return si==sn and ti<tn; } int lower_bound(Seq t){ int l=0,r=s.size()+1; while(l+1<r){ int m=(l+r)>>1; if(lt_substr(t,sa[m],0)) l=m; else r=m; } return r; } int upper_bound(Seq t){ t.back()++; int res=lower_bound(t); t.back()--; return res; } // O(|t| \log|s|) int count(Seq t){ return upper_bound(t)-lower_bound(t); } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ vector<int> vs({1, 2, 3, 1, 2, 1}); SuffixArray sa(vs); for(int i=0;i<=(int)vs.size();i++) cout<<sa[i]<<endl; cout<<sa.count({1})<<endl; cout<<sa.count({1, 2})<<endl; cout<<sa.count({1, 2, 3})<<endl; cout<<sa.count({1, 2, 3, 4})<<endl; return 0; } #endif #line 1 "segtree/basic/ushi.cpp" #line 3 "segtree/basic/ushi.cpp" using namespace std; #endif //BEGIN CUT HERE template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ if(a>=b) return ti; T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } template<typename C> int max_right(int s,C &check,T &acc,int k,int l,int r){ if(l+1==r){ acc=f(acc,dat[k]); return check(acc)?-1:k-n; } int m=(l+r)>>1; if(m<=s) return max_right(s,check,acc,(k<<1)|1,m,r); if(s<=l and check(f(acc,dat[k]))){ acc=f(acc,dat[k]); return -1; } int vl=max_right(s,check,acc,(k<<1)|0,l,m); if(~vl) return vl; return max_right(s,check,acc,(k<<1)|1,m,r); } // max t s.t. check(query(s,t)) // O(\log N) template<typename C> int max_right(int s,C &check){ assert(s<n and check(ti) and not check(query(s,n))); T acc=ti; return max_right(s,check,acc,1,0,n); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 9 "test/aoj/2644.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); string s; int m; cin>>s>>m; SuffixArray sa(s); using P = pair<int, int>; auto f=[](P a,P b){ return P(max(a.first,b.first), min(a.second,b.second)); }; int n=s.size()+1; SegmentTree<P> seg(f,P(-1,n+1)); vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(sa[i],sa[i]); seg.build(vp); for(int i=0;i<m;i++){ string x,y;cin>>x>>y; int lx=sa.lower_bound(x); int rx=sa.upper_bound(x); int ly=sa.lower_bound(y); int ry=sa.upper_bound(y); int ans; if(rx-lx<=0||ry-ly<=0) ans=0; else{ int a=seg.query(ly,ry).first; int b=seg.query(lx,rx).second; if(b+(int)x.size()>a+(int)y.size()) ans=0; else ans=a-b+y.size(); } cout<<ans<<"\n"; } cout<<flush; return 0; }