Language: C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef unsigned long long llu;

const llu B = 37ULL;

int best[10010];
int M[20000002], m;
vector<llu> h[2002];
string str[2002];
vector<int> acc_sz[20000002], nxt[20000002];
int last[20000002];
vector<llu> acc_hash[20000002];
llu pot[1000010];

void process(int idx, int t, int s) {
  int i, sz = str[s].size();
  acc_sz[idx].clear();
  acc_hash[idx].clear();
  nxt[idx].clear();
  acc_sz[idx].push_back(sz); acc_hash[idx].push_back(h[s][str[s].size()]); nxt[idx].push_back(best[t-sz]);
  for (i=1; nxt[idx][i-1]; i++) {
    int p = min(i-1, last[nxt[idx][i-1]]);
    /*acc_sz[idx][i] = acc_sz[idx][i-1] + acc_sz[nxt[idx][i-1]][p];
    acc_hash[idx][i] = acc_hash[idx][i-1] * pot[acc_sz[nxt[idx][i-1]][p]] + acc_hash[nxt[idx][i-1]][p];
    nxt[idx][i] = nxt[nxt[idx][i-1]][p];*/
    acc_sz[idx].push_back(acc_sz[idx][i-1] + acc_sz[nxt[idx][i-1]][p]);
    acc_hash[idx].push_back(acc_hash[idx][i-1] * pot[acc_sz[nxt[idx][i-1]][p]] + acc_hash[nxt[idx][i-1]][p]);
    nxt[idx].push_back(nxt[nxt[idx][i-1]][p]);
  }
  last[idx] = i-1;
}

llu calc(int idx, int pos, int s, char &ch) {
  llu hs = 0ULL;
  while (1) {
    int j = 0;
    while (acc_sz[idx][j] < pos) j++;

    if (acc_sz[idx][j] == pos) {
      hs = hs * pot[acc_sz[idx][j]] + acc_hash[idx][j];
      ch = str[M[nxt[idx][j]]][0];
      break;
    }

    if (j == 0) {
      hs = hs * pot[pos] + h[s][pos];
      ch = str[s][pos];
      break;
    }

    hs = hs * pot[acc_sz[idx][j-1]] + acc_hash[idx][j-1];
    pos -= acc_sz[idx][j-1];
    idx = nxt[idx][j-1];
    s = M[idx];
  }
  
  return hs;
}

int main() {
  int n,k;
  cin>>n>>k;

  pot[0] = 1ULL;
  for (int i=1; i<1000010; i++)
    pot[i] = pot[i-1] * B;

  for (int i=0; i<n; i++) {
    cin>>str[i];
    h[i].resize(str[i].size()+1);
    h[i][0] = 0ULL;
    for (int j=0; j<int(str[i].size()); j++)
      h[i][j+1] = h[i][j]*B + (llu)(str[i][j]-'a'+1);
  }

  memset(best, -1, sizeof(best));
  best[0] = 0;
  M[0] = 0; m = 1;
  for (int i=n-1; i>=0; i--) {
    for (int t=k; t-int(str[i].size())>=0; t--) {
      int j = t - str[i].size();
      if (best[j] == -1) continue;
      if (best[t] == -1) {
        process(m, t, i);
        M[m] = i;
        best[t] = m++;
        continue;
      }

      process(m, t, i);

      int hi=t,lo=1,mid,lcp=0;
      int it = best[t];
      char ch_old, ch_new;
      bool is_better = str[i][0] < str[M[it]][0];
      while (lo <= hi) {
        mid = (lo+hi) >> 1;
        if (calc(m, mid, i, ch_new) == calc(it, mid, M[it], ch_old)) {
          lcp = mid;
          lo = mid+1;
          is_better = ch_new < ch_old;
        } else {
          hi = mid-1;
        }
      }

      if (lcp != t && is_better) {
        process(m, t, i);
        M[m] = i;
        best[t] = m++;
      }
    }
  }

  int idx = best[k];
  while (idx) {
    cout << str[M[idx]];
    idx = nxt[idx][0];
  }
  cout << endl;

  return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:81:3: error: 'memset' was not declared in this scope
   81 |   memset(best, -1, sizeof(best));
      |   ^~~~~~
a.cc:4:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    3 | #include <vector>
  +++ |+#include <cstring>
    4 |