library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub beet-aizu/library

:heavy_check_mark: test/aoj/2644.test.cpp

Depends on

Code

// 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;
}
Back to top page