Language: C++

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


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

  RollingHash():n(-1){};
  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)
  
  int getDiffIdx(int a,RollingHash &B,int b){
    int L = 0, R = B.n+1;
    while(L+1<R){
      int M = (L+R)/2;
      a+M>n || get(a,a+M) != B.get(b,b+M)? R=M:L=M;
    }
    return L;
  }
};


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;
  ll n_;
  vector<ll> dat;
  vector<data> td;
  
  RMQ(){n=-1;}
  RMQ(int n_):n_(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_),assert(a >=0 && b >=0);
    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);};
};


class SA{
public:
  string S;
  int n;
  vector<int> sa;
  
  SA():n(-1){}
  SA(string S):S(S),n(S.size()),sa(n){  
    vector<int> rnk(n);
    vector<int> tmp(n);
    for(int i=0;i<n;i++) sa[i]=i;
    for(int i=0;i<n;i++) rnk[i] = S[i];
    
    //k文字についてソートされているところから、2k文字でソート
    for(int Len=1;Len<=n;Len*=2){
      
      //(rnk[i],rnk[i+k])と(rnk[j],rnk[j+k])を比較
      auto compare_sa=[&](const int &i,const int &j){
        if(rnk[i]!=rnk[j])return rnk[i]<rnk[j];
        int ri=i+Len<=n?rnk[i+Len]:-1;
        int rj=j+Len<=n?rnk[j+Len]:-1;
        return ri<rj;
      };
      
      sort(sa.begin(),sa.end(),compare_sa);

      //いったんtmpに次のランクを計算して、rnkに代入
      for(int i=1;i<n;i++)
        tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
      rnk = tmp;
    }
  }

  int lower_bound(string T){
    assert(n >= 0);
    int L=-1,R=S.length();
    while(L+1<R){
      int M = (L+R)/2;
      compare(sa[M])<0? L = M:R = M;
    }
    return R;
  } 

  int upper_bound(string T){return lower_bound(T+char('z'+ 1));} 
  
  
  //Sの文字列からTの文字列があるか検索する
  bool contain(string T){
    assert(n>=0);
    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;
  }
};


signed main(){

  string s;
  cin>>s;
  int n;
  cin>>n;
  vector<string> p(n);
  cin>>p;

  sort(p.begin(),p.end(),[](const string &a,const string &b){return a.size() > b.size();});

  int len = s.size();  
  SA sa(s);
  RMQ rmq(len);
  for(auto t:p){
    int l = sa.lower_bound(t);
    int r = sa.upper_bound(t);
    rmq.update(l,r,t.size());
  }
  
  vector<P> A;
  for(int i=0;i<len;i++){
    int l = sa.sa[i];
    int r = l + rmq.find(i,i+1);
    if(r == l+INF) continue;
    A.push_back(P(r,l));
  }

  sort(A.begin(),A.end());
  int ans = 0;
  int rmax = 0;
  for(auto p:A){
    int r,l; tie(r,l) = p;
    if(l >= rmax) ans++, rmax = r;
  }

  cout<<ans<<endl;
  
  return 0;
}



Compiler output:
a.cc:23:39: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
   23 | ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
      |                                       ^~~~
a.cc:24:39: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
   24 | istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
      |                                       ^~~~
a.cc:25:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   25 | void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
      |            ^~~~
a.cc: In member function 'long long int SA::lower_bound(std::string)':
a.cc:146:7: error: 'compare' was not declared in this scope
  146 |       compare(sa[M])<0? L = M:R = M;
      |       ^~~~~~~