Language: C++

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000005

class RollingHash{
public:
  typedef unsigned long long ull;
  ull B = 1777771; //ハッシュ基数
  int n;
  string s;
  vector<ull> hash;
  vector<ull> k;

  RollingHash(){};
  RollingHash(string s):n(s.size()),s(s),hash(n+1),k(n+1){
    for(int i=0;i<n;i++) hash[i+1] = hash[i] * B + s[i];
    k[0] = 1;
    for(int i=1;i<=n;i++) k[i] = k[i-1] * B;
  }

  ull get(int l,int r){assert(0<=l && r<=n);return hash[r] - hash[l] * k[r-l];}//[l,r)
};

class RMQ{
public : 
  typedef pair<int,int> P;
  typedef long long ll;
  const ll INF = 1LL<<55;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n;
  vector<ll> dat;
  vector<data> td;
  
  RMQ(){n=-1;}
  RMQ(int n_){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)の値をxに変更 update(a,b,x)
  ll update(int a,int b,int x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a < n && b <= n);
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      dat[k*2+1]=dat[k*2+2]=td[k].value;
      td[k*2+1]=td[k*2+2]=(data){1,td[k].value};
      td[k].type=0;
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)の最小値を得る find(a,b);
  ll find(int a,int b){return update(a,b,0,false);};
};

//Suffix_Array
//O(|T|log|S|) Sの文字列からTの文字列があるか検索
#define rank Asadfsadfs

class SA{
public:
  int Len,n;
  vector<int> rank;
  vector<int> tmp;
  vector<int> sa;
  string S;
  RollingHash A;
  
  SA(){
    rank.resize(MAX_N+1);
    tmp.resize(MAX_N+1);
    sa.resize(MAX_N+1);
  }
  
  //(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
  bool compare_sa(int i,int j){
    if(rank[i]!=rank[j])return rank[i]<rank[j];
    int ri=i+Len<=n?rank[i+Len]:-1;
    int rj=j+Len<=n?rank[j+Len]:-1;
    return ri<rj;
  }
  
  //文字列Sの接尾辞配列を構築
  void construct_sa(string S){
    A = RollingHash(S);
    this->S = S;
    n=S.length();
    //最初は一文字、ランクは文字コードにする
    for(int i=0;i<=n;i++){
      sa[i]=i;
      rank[i]=i<n?S[i]:-1;
    }
    //k文字についてソートされているところから、2k文字でソート
    for(Len=1;Len<=n;Len*=2){
      sort(sa.begin(),sa.begin()+n+1,[&] (int i,int j){
          if(rank[i]!=rank[j])return rank[i]<rank[j];
          int ri=i+Len<=n?rank[i+Len]:-1;
          int rj=j+Len<=n?rank[j+Len]:-1;
          return ri<rj;
        });
      //いったんtmpに次のランクを計算して、rankに代入
      tmp[sa[0]]=0;
      for(int i=1;i<=n;i++)
        tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
      for(int i=0;i<=n;i++)rank[i]=tmp[i];
    }
  }

  //Sの文字列からTの文字列があるか検索する
  bool contain(string S,string T){
    int left=0,right=S.length();
    while(right-left>1){
      int mid=(left+right)/2;
      if(S.compare(sa[mid],T.length(),T)<0)left=mid;
      else right=mid;
    }
    return S.compare(sa[right],T.length(),T)==0;
  }
  
  int compare(int a,int b,int n,RollingHash &A ,RollingHash &B,string &T){
    int L = 0, R = n;
    while(L+1<R){
      int M = (L+R)/2;
      if(a + M > (int)S.size() || A.get(a,a+M) != B.get(b,b+M)) R = M;
      else L = M;
    }

    if(L == n) return 1;
    if(S[a+L] < T[b+L]) return -1;
    return 1;
  }

  int Lower(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>=0) R = M;
      //if(S.compare(sa[M],T.size(),T)>=0) R = M;
      else L = M+1;
    }  
    return L;
  }
  
  int Upper(string &T){
    int L=0,M,R=S.size();
    RollingHash H(T);
    while(L<R){
      M = (L+R)/2;
      if(compare(sa[M],0,T.size(),A,H,T)>0) R = M;
      //if(S.compare(sa[M],T.size(),T)>0) R = M;
      else L = M+1;
    }
    
    return L;
  }

};

string s, p[100005];
SA sa = SA();

int Lower(string t){
  
  int l = 0, r = (int)s.size() + 1;
  
  while( l + 1 < r ){
    
    int m = ( l + r ) / 2;
    int idx = sa.sa[m];
    
    if( s.substr(idx) < t ) l = m;
    else r = m;
    
  }

  return r;
} // sa で　初めてt以上になるところのidx

typedef pair<int,int> P;

int n;

int main(){
  
  cin>>s;

  cin>>n;
  
  for(int i=0;i<n;i++) cin>>p[i];
  
  sort( p, p+n, [](const string &a,const string &b){
      return a.size() > b.size();
    });
  
  sa.construct_sa(s);
  
  int len = s.size();
  
  RMQ rmq = RMQ(len+1);
  
  for(int i=0;i<len+1;i++) rmq.update(i,i+1,0);
  
  for(int i=0;i<n;i++){
    
    string t = p[i];
    f
    if( Lower(t) >= len + 1 ) continue;
      
    rmq.update( Lower(t), Lower(t+'{'), (int)t.size() );
    
  }
  
  vector<P> v;
  
  for(int i=1;i<len+1;i++){
    
    v.push_back(P( rmq.find( i, i+1 ) + sa.sa[i] - 1 , sa.sa[i] ));
    
  }
  
  sort(v.begin(), v.end());
  
  int ans = 0, maxr = -1;
  
  for(int i=0;i<len;i++){
    
    int l = v[i].second, r = v[i].first;
    
    if( l > r ) continue;
    
    if( maxr < l ) ans++;
    
    maxr = r;
  }
  
  cout<<ans<<endl;
  
  return 0;
}



Compiler output:
a.cc: In function 'int main()':
a.cc:225:5: error: 'f' was not declared in this scope
  225 |     f
      |     ^