Language: C++

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

#define MAX_W (20+1)
const int infty = 1<<28;

struct Node{
  int dp[MAX_W];
  int v;
  int minvind;
  Node(){
    v = infty;
    minvind = infty;
    for(int i = 0; i < MAX_W; ++i){
      dp[i] = 0;
    }
  }
};

struct SAComp{
  const int h,*g;
  SAComp(int h,int *g):h(h),g(g){}
  bool operator()(int a,int b){
    return a==b?false:g[a]!=g[b]?g[a]<g[b]:g[a+h]<g[b+h];
  }
};

int *buildSA(const char *t, int n)
{
  const int len = n+1;
  int *g = new int[len];
  int *b = new int[len];
  int *v = new int[len];

  for(int i=0;i<len;++i){v[i]=i;g[i]=t[i];}
  b[0]=b[n]=0;
  
  sort(v,v+len,SAComp(0,g));
  for(int h=1;b[n]!=n;h*=2){
    SAComp comp(h,g);
    sort(v,v+len,comp);
    for(int i=0;i<n;++i)b[i+1]=b[i]+comp(v[i],v[i+1]);
    for(int i=0;i<len;++i)g[v[i]]=b[i];
  }

  delete [] g;
  delete [] b;
  return v;
}

int find(const char *t, int n, const char *p, int m, int *sa)
{
  int a=0;
  int b=n;
  while(a+1<b){
    int c=(a+b)/2;
    if(strncmp(t+sa[c],p,m)<0)
      a=c+1;
    else
      b=c;
  }
  if(0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0) return a;
  return (0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)?b:-1;
}

int last_find(const char *t, int n, const char *p, int m, int *sa)
{
  int a=0;
  int b=n;
  while(a+1<b){
    int c=(a+b)/2;
    if(strncmp(t+sa[c],p,m)<=0)
      a=c;
    else
      b=c-1;
  }
  if(0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)return b;
  return (0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0)?a:-1;
}

int smtree_size;
Node *smtree;

void buildST(int n_){
  smtree_size=1;
  while(smtree_size<n_)smtree_size*=2;
  smtree = new Node[2*smtree_size-1];
  for(int i=0;i<2*smtree_size-1;++i){
    smtree[i]=Node();
  }
}

void smtree_update(int k, const Node &a){
  k+=smtree_size-1;
  smtree[k]=a;
  while(k>0){
    k=(k-1)/2;
    smtree[k] = a;
    for(int wk = 0; wk < MAX_W; ++wk){
      for(int w = 0; w <= wk; ++w){
        smtree[k].dp[wk] = max( smtree[k].dp[wk],
                                smtree[k*2+1].dp[w] + smtree[k*2+2].dp[wk-w] );
      }
    }
    if( smtree[k*2+1].v < smtree[k*2+2].v ){
      smtree[k].v = smtree[k*2+1].v;
      smtree[k].minvind = smtree[k*2+1].minvind;
    }else{
      smtree[k].v = smtree[k*2+2].v;
      smtree[k].minvind = smtree[k*2+2].minvind;
    }
  }
}

Node smtree_query(int a, int b, int k, int l, int r){
  if(r<=a||b<=l)return Node();
  if(a<=l&&r<=b){
    return smtree[k];
  }
  else{
    Node vl=smtree_query(a,b,k*2+1,l,(l+r)/2);
    Node vr=smtree_query(a,b,k*2+2,(l+r)/2,r);

    Node ret;
    
    for(int wk = 0; wk < MAX_W; ++wk){
      for(int w = 0; w <= wk; ++w){
        ret.dp[wk] = max( ret.dp[wk], vl.dp[w] + vr.dp[wk-w] );   
      }
    }
    if( vl.v < vr.v ){
      ret.v = vl.v;
      ret.minvind = vl.minvind;
    }else{
      ret.v = vr.v;
      ret.minvind = vr.minvind;
    }
    return ret;
  }
}

int main()
{
  while(true){
    int ind = 0;
    int N;
    int W;
    int tree_len;
    int *SA;
    int *revSA;
    int *IND;
    pair<int,int> *V;
    string text;

    cin >> N >> W;
    if( N == 0 && W == 0 ) break;
    V = new pair<int,int>[N]; // value, weight

    // N
    for(int i = 0; i < N; ++i){
      string s;
      cin >> s;
      s += "$";
      text += s;
      cin >> V[i].first >> V[i].second;
    }
    tree_len = text.length() + 1;

    // LEN * (lg LEN) ^ 2
    SA = buildSA(text.c_str(), text.length());
    revSA = new int[text.length()];
    IND = new int[text.length()];

    // LEN
    for(int i = 0; i < (int)text.length(); ++i){
      IND[i] = ind;
      if(text[i]=='$'){
        ++ind;
      }
    }

    // LEN * (W + W*W*lg LEN)
    // SA[0] = Úö«Å¬Ì text index
    buildST(tree_len);
    for(int i = 0; i <= (int)text.length(); ++i){
      Node node;
      if( SA[i] == (int)text.length() ){
        ind = N-1;
      }else{
        ind = IND[SA[i]];
      }
      // cout << i << " : " << SA[i] << " : " << text.c_str() + SA[i] << " ind : " << ind << " value : " << V[ind].first << " weight : " << V[ind].second << endl;
      node.v = V[ind].first;
      node.minvind = i;
      for(int w = 0; w < MAX_W; ++w){
        if( V[ind].second <= w ){
          node.dp[w] = V[ind].first;
        }
      }
      smtree_update(i,node);
    }
    
    int Q;
    cin >> Q;
    // Q * (2*QS*lg LEN + W*W*lg LEN + W)
    for(int i = 0; i < Q; ++i){
      int res = -1;
      int l,r;
      string q;
      cin >> q;
      
      l = find(text.c_str(),text.length(),q.c_str(),q.length(),SA);
      r = last_find(text.c_str(),text.length(),q.c_str(),q.length(),SA);
      if( l >= 0 ){
        Node ans = smtree_query(l,r+1,0,0,smtree_size);
        for(int w = 0; w <= W; ++w){
          res = max( res, ans.dp[w] );
        }
        // cout << "QUERY: " << q << " MINWIND : " << ans.minvind << endl;
        if(ans.minvind<infty)
          smtree_update( ans.minvind, Node() );
        else{
          res = -1;
        }
      }
      cout << res << endl;
    }

    delete [] V;
    delete [] SA;
    delete [] IND;
    delete [] smtree;
  }
  return 0;
}

Compiler output:
a.cc: In function 'int find(const char*, int, const char*, int, int*)':
a.cc:60:8: error: 'strncmp' was not declared in this scope
   60 |     if(strncmp(t+sa[c],p,m)<0)
      |        ^~~~~~~
a.cc:3:1: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    2 | #include<algorithm>
  +++ |+#include <cstring>
    3 | #include<string>
a.cc:65:18: error: 'strncmp' was not declared in this scope
   65 |   if(0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0) return a;
      |                  ^~~~~~~
a.cc:65:18: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:66:23: error: 'strncmp' was not declared in this scope
   66 |   return (0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)?b:-1;
      |                       ^~~~~~~
a.cc:66:23: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc: In function 'int last_find(const char*, int, const char*, int, int*)':
a.cc:75:8: error: 'strncmp' was not declared in this scope
   75 |     if(strncmp(t+sa[c],p,m)<=0)
      |        ^~~~~~~
a.cc:75:8: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:80:18: error: 'strncmp' was not declared in this scope
   80 |   if(0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)return b;
      |                  ^~~~~~~
a.cc:80:18: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:81:23: error: 'strncmp' was not declared in this scope
   81 |   return (0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0)?a:-1;
      |                       ^~~~~~~
a.cc:81:23: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'