Language: C++

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cassert>
#include<map>

using namespace std;

#define MAXW (20+1)

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 solve(pair<int,int> vitems[], int n, int W){
  int ret = 0;
  int dp[n+1][W+1];

  for(int i = 0; i < n+1; ++i){
    for(int j = 0; j < W+1; ++j){
      dp[i][j] = 0;
    }
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j <= W; ++j){
      int v = vitems[i].first;
      int w = vitems[i].second;

      if( j-w < 0 ){
        dp[i+1][j] = dp[i][j];
      }else{
        dp[i+1][j] = max( dp[i][j], dp[i][j-w]+v );
      }
    }
  }

  for(int j = 0; j <= W; ++j){
    ret = max(ret, dp[n][j]);
  }

  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;
    map<string,int> sol;

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

    // 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;
      }
    }
    
    int Q;
    cin >> Q;
    // Q * (2*QS*lg LEN + W*W*lg LEN + W)
    pair<int,int> ws[N];

    for(int i = 0; i < Q; ++i){
      int res = -1;
      int l,r;
      string q;
      cin >> q;

      if( sol.find(q)==sol.end() ){
        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);
        //cout << l << ' ' << r << endl;
        assert(l>=0);
        if(l>=0){
          int num = 0;
          //cout << q << endl;
          for(int k = l; k <= r; ++k){
            //cout << text.c_str()+SA[k] << ' ' << SA[k] << ' ' << IND[SA[k]] << ' ' << endl;
            ws[num++] =  V[IND[SA[k]]];
          }
        res = solve(ws,num,W);
        }
      }else{
        res = sol[q];
      }
      sol[q] = res;
      cout << res << endl;
    }

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

Compiler output:
a.cc: In function 'int find(const char*, int, const char*, int, int*)':
a.cc:49:8: error: 'strncmp' was not declared in this scope
   49 |     if(strncmp(t+sa[c],p,m)<0)
      |        ^~~~~~~
a.cc:7:1: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    6 | #include<map>
  +++ |+#include <cstring>
    7 | 
a.cc:54:18: error: 'strncmp' was not declared in this scope
   54 |   if(0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0) return a;
      |                  ^~~~~~~
a.cc:54:18: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:55:23: error: 'strncmp' was not declared in this scope
   55 |   return (0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)?b:-1;
      |                       ^~~~~~~
a.cc:55: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:64:8: error: 'strncmp' was not declared in this scope
   64 |     if(strncmp(t+sa[c],p,m)<=0)
      |        ^~~~~~~
a.cc:64:8: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:69:18: error: 'strncmp' was not declared in this scope
   69 |   if(0<=b&&b<=n&&strncmp(t+sa[b],p,m)==0)return b;
      |                  ^~~~~~~
a.cc:69:18: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:70:23: error: 'strncmp' was not declared in this scope
   70 |   return (0<=a&&a<=n&&strncmp(t+sa[a],p,m)==0)?a:-1;
      |                       ^~~~~~~
a.cc:70:23: note: 'strncmp' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'