Dictionary

input/code.cpp: In function 'int main()':
input/code.cpp:48:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();++i)s[i]=v[i];
                        ^
input/code.cpp:81:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=v.size();++i){
                         ^

#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <map>
#include <cstring>
#include <iostream>
using namespace std;
vector<int> get_suffix_array(const vector<int>&seq){
  if(seq.size()==0)return vector<int>();
  vector<int> cur = seq;
  int n = cur.size();
  for(int length = 1;;length*=2){
    vector<pair<pair<int,int>,int>> pairs(n);
    for(int i=0;i<n;++i){
      pairs[i]={{cur[i],i+length<n?cur[i+length]:-1},i};
    }
    sort(pairs.begin(),pairs.end());
    int code=0;
    for(int i=0;i<n;i++){
      if(i!=0&&pairs[i].first!=pairs[i-1].first)
        ++code;
      cur[pairs[i].second]=code;
    }
    if(code==n-1){
      vector<int> result(n);
      for(int i=0;i<n;i++)result[i]=pairs[i].second;
      return result;
    }
  }
}

int prefcmp(const char* a, const char* b){
  while(*a&&*b){
    if(*a<*b)return -1;
    if(*a>*b)return 1;
    ++a,++b;
  }
  if(*a)return 1;
  return 0;
}
typedef long long ll;

int main(){
  string v;
  cin>>v;
  vector<int> s(v.size(),0);
  for(int i=0;i<v.size();++i)s[i]=v[i];
  auto sa = get_suffix_array(s);
  int m;
  cin>>m;
  vector<map<int,ll>> cnts;
  cnts.resize(v.size()+2);
  for(int i=0;i<m;++i){
    string w;
    cin>>w;
    int a=0,b=sa.size();
    while(b-a>1){
      int c=(a+b)>>1;
      int p=prefcmp(w.c_str(),v.c_str()+sa[c]);
      if(p<0)b=c;
      else if(p>0)a=c;
      else a=c;
    }
    int u=a;
    a=0,b=u;
    while(b-a>1){
      int c=(a+b)>>1;
      int p=prefcmp(w.c_str(),v.c_str()+sa[c]);
      if(p<0)b=c;
      else if(p>0)a=c;
      else b=c;
    }
    if(prefcmp(w.c_str(),v.c_str()+sa[a])!=0)++a;
    int l=a;
    for(;l<=u;++l)++cnts[sa[l]+w.size()][sa[l]];
  }
  vector<ll> r;
  r.resize(v.size()+1);
  r[0]=1;
  for(int i=1;i<=v.size();++i){
    for(auto& it : cnts[i])r[i]=(it.second*r[it.first]+r[i])%(1000000007);
  }
  cout<<r.back()<<'\n';
  return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: RUNTIME ERROR

Test 3

Verdict: ACCEPTED