Counting Words

input/code.cpp: In function 'int main()':
input/code.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<s.size(); ++i) k.push_back(s[i]-'?');
                          ^

#include <bits/stdc++.h>
using namespace std;
string s;
int w;

vector<int> suffixArray(vector<int> s, int S){
  int n=s.size(); int N=n+S;
  vector<int> sa(n), ra(n);
  for (int i=0; i<n; ++i) { sa[i]=i; ra[i]=s[i];}
  for (int k=0; k<n; k?k*=2:k++){
    vector<int> nsa(sa), nra(n), cnt(N);
    for (int i=0; i<n; ++i) nsa[i]=(nsa[i]-k+n)%n;
    for (int i=0; i<n; ++i) cnt[ra[i]]++;
    for (int i=1; i<N; ++i) cnt[i]+=cnt[i-1];
    for (int i=n-1; i>=0; --i) sa[--cnt[ra[nsa[i]]]]=nsa[i];
    int r=0;
    for (int i=1; i<n; ++i){
      if (ra[sa[i]]!=ra[sa[i-1]]) ++r;
      else if (ra[(sa[i]+k)%n]!=ra[(sa[i-1]+k)%n]) ++r;
      nra[sa[i]]=r;
    }
    ra=nra;
  }
  return sa;
}


int id[403030];
int ide[403030];
int ans[202020];


int t[101010];

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> s;
  int n;
  n=s.size();
  cin >> w;
  
  s.push_back('@');
  for (int i=1; i<=w; ++i){
    string t;
    cin >> t;
    id[s.size()]=i;
    
    s+=t;
    s.push_back('?');
    
    ide[s.size()]=i;
    
    s+=t;
    s.push_back('[');
  }
  
  vector<int> k;
  for (int i=0; i<s.size(); ++i) k.push_back(s[i]-'?');
  vector<int> sa=suffixArray(k, 30);
  
  int ss=0;
  for (auto k : sa) {
    if (id[k]){
      t[id[k]]=ss;
    }else if (ide[k]){
      ans[ide[k]]=ss-t[ide[k]];
    }else  if (k<n){
      ++ss;
    }
  }
  
  for (int i=1; i<=w; ++i) cout << ans[i] << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED