萌新求助 wa on #65
查看原帖
萌新求助 wa on #65
771171
Egg_laying_master楼主2022/8/29 21:50
#include <bits/stdc++.h>

#define db(x) cerr << #x << '=' << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define dbg debug("*** Passing [%s] in LINE %d\n", __FUNCTION__, __LINE__)

using namespace std;

bool m_st;

/* ---------- Line ---------- */

typedef unsigned long long ull;

const int kMaxN = 1e5 + 5, kMaxS = 1e6 + 5;

int n, msz;
int sz[kMaxN];
ull hs[kMaxS], pw[kMaxS];
char ans[kMaxS];
vector<string> s;
vector<ull> hsh[kMaxN];

ull gethash(int l, int r) {
  return hs[r] - hs[l - 1] * pw[r - l + 1];
}
ull gethash(int x, int l, int r) {
  return hsh[x][r] - hsh[x][l - 1] * pw[r - l + 1];
}

/* ---------- Line ---------- */

bool m_ed;

int main() {
  cin >> n;
  s.resize(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    sz[i] = s[i].size();
    msz += sz[i];
    hsh[i].resize(sz[i] + 1);
    s[i] = " " + s[i];
  }
  pw[0] = 1ull;
  for (int i = 1; i <= msz; ++i) {
    pw[i] = pw[i - 1] * 291143;
  }
  for (int i = 1; i <= sz[1]; ++i) {
    hs[i] = hs[i - 1] * 291143 + s[1][i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= sz[i]; ++j) {
      hsh[i][j] = hsh[i][j - 1] * 291143 + s[i][j];
    }
  }
  int nw = sz[1];
  for (int i = 1; i <= nw; ++i) {
    ans[i] = s[1][i];
  }
  for (int i = 2; i <= n; ++i) {
    int idx = 0;
    for (int j = min(sz[i], nw); j; --j) {
      if (gethash(nw - j + 1, nw) == gethash(i, 1, j)) {
        idx = j; break ;
      }
    }
    for (int j = idx + 1; j <= sz[i]; ++j) {
      hs[nw + j - idx] = hs[nw + j - idx - 1] * 291143 + s[i][j];
      ans[nw + j - idx] = s[i][j];
    }
    nw += sz[i] - idx;
  }
  for (int i = 1; i <= nw; ++i) {
    putchar(ans[i]);
  }
  putchar('\n');
  return 0;
}
2022/8/29 21:50
加载中...