結果

問題 No.430 文字列検索
ユーザー 👑 tute7627tute7627
提出日時 2019-10-16 21:27:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 5,659 bytes
コンパイル時間 2,136 ms
コンパイル使用メモリ 189,200 KB
実行使用メモリ 6,144 KB
最終ジャッジ日時 2024-11-10 00:36:17
合計ジャッジ時間 2,670 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 10 ms
6,016 KB
testcase_02 AC 7 ms
5,248 KB
testcase_03 AC 8 ms
6,016 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 8 ms
6,144 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 12 ms
5,888 KB
testcase_12 AC 11 ms
5,888 KB
testcase_13 AC 12 ms
5,888 KB
testcase_14 AC 11 ms
5,632 KB
testcase_15 AC 10 ms
5,504 KB
testcase_16 AC 7 ms
5,248 KB
testcase_17 AC 6 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs 
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = m - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
//const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
struct SuffixArray{
  ll size;
  string str;
  vector<ll>data;
  SuffixArray(string S):size(S.size()),str(S){
    str += '$';
    vector<ll>input(str.size());
    for(ll i=0;i<str.size();i++)input[i] = str[i];
    data = induced_sort(input, 200);
    data.erase(data.begin()); data.push_back(size);
    str.pop_back();
  }
  vector<ll> induced_sort(vector<ll>t, ll kind){
    ll sz = t.size();
    vector<bool>ls(sz);//trueはL型,falseはS型
    for(ll i = sz-1;i>=0;i--){
      if(i==sz-1)ls[i] = false;
      else{
        if(t[i]!=t[i+1])ls[i] = (t[i] > t[i+1]);
        else ls[i] = ls[i+1];
      }
    }
    vector<ll>cnt(kind);
    for(ll i=0;i<sz;i++)cnt[t[i]]++;
    vector<P>lr(kind,MP(-1,-1));
    for(ll i=1;i<kind;i++){
      if(cnt[i]==0)lr[i] = lr[i-1];
      else lr[i] = make_pair(lr[i-1].se + 1, lr[i-1].se + cnt[i]);
    }
    vector<ll>lmsidx,ret(sz,-1);
    for(ll i=0;i<sz-1;i++){
      if(ls[i]&&!ls[i+1]){
        ret[lr[t[i+1]].fi+cnt[t[i+1]]-1]=i+1;
        cnt[t[i+1]]--;
        lmsidx.push_back(i+1);
      }
    }
    fill(ALL(cnt),0);
    for(ll i=0;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].fi+cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
        if(i!=0&&!ls[ret[i]])ret[i]=-1;
      }
    }
    fill(ALL(cnt),0);
    for(ll i=sz-1;i>=1;i--){
      if(ret[i]>=1&&!ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].se-cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
      }
    }
    vector<ll>rev_lmsidx(sz,-1),lmsinput(lmsidx.size(),-1);
    for(ll i=0;i<lmsidx.size();i++)rev_lmsidx[lmsidx[i]] = i;
    ll kindnum=1; 
    lmsinput[rev_lmsidx[ret[0]]] = 1;
    vector<ll>comp(t.begin()+ret[0],t.end());
    for(ll i=1;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]&&!ls[ret[i]]){
        vector<ll>tmp(t.begin()+ret[i],t.begin()+lmsidx[rev_lmsidx[ret[i]]+1]+1); 
        if(comp != tmp){
          kindnum++;
          comp = tmp;
        }
        lmsinput[rev_lmsidx[ret[i]]] = kindnum;
      }
    }
    vector<ll>output;
    if(kindnum==lmsidx.size()){
      output.assign(kindnum,-1);
      for(ll i=0;i<lmsinput.size();i++)output[lmsinput[i]-1]=i;
    }
    else output = induced_sort(lmsinput,kindnum+1);
    
    fill(ALL(cnt),0), fill(ALL(ret),-1);
    for(ll i=output.size()-1;i>=0;i--){
      ll tmp=lmsidx[output[i]];
      ret[lr[t[tmp]].se - cnt[t[tmp]]]=tmp;
      cnt[t[tmp]]++;
    }
    fill(ALL(cnt),0);
    for(ll i=0;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].fi+cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
        if(i!=0&&!ls[ret[i]])ret[i]=-1;
      }
    }
    fill(ALL(cnt),0);
    for(ll i=sz-1;i>=1;i--){
      if(ret[i]>=1&&!ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].se-cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
      }
    }
    return ret;
  }
  ll operator[](ll x) const {
    return data[x];
  }
  ll lower_bound(string x){
    ll le=-1,ri=str.size();
    while(ri-le>=2){
      ll mid=(le+ri)/2;
      ll cnt=0;
      while(cnt<x.size()&&data[mid]+cnt<str.size()
        &&x[cnt]==str[data[mid]+cnt])cnt++;
      if(cnt==x.size())ri=mid;
      else if(data[mid]+cnt==str.size())le=mid;
      else if(x[cnt]<=str[data[mid]+cnt])ri=mid;
      else le=mid;
    }
    return ri;
  }
  ll upper_bound(string x){
    x.back()++;
    return lower_bound(x);
  }
};
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout<<fixed<<setprecision(10);
  ll res=0,buf=0;
  bool judge = true;
  string s;cin>>s;
  SuffixArray sa(s);
  ll m;cin>>m;
  while(m--){
    string c;cin>>c;
    res+=sa.upper_bound(c)-sa.lower_bound(c);
  }
  cout<<res<<endl;
  return 0;
}
0