WA on #4 求助
查看原帖
WA on #4 求助
502658
Ray662楼主2023/3/14 22:18
#include <bits/stdc++.h>
#define int long long
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define _all(i, a, b)  for (int i = (a); i >= (b); i -- )
using namespace std;
const int N = 1e5 + 5, base = 137173, P = 1e9 + 7;
int n, p[N], hi[N], hj[N];
string ans, s[N];
inline int Hash(int q[], int l, int r) { return ((q[r] - q[l - 1] * p[r - l + 1]) % P + P) % P; }
signed main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	_for (i, 1, n)  cin >> s[i];
	p[0] = 1ll;
	_for (i, 1, n)  p[i] = (p[i - 1] * base) % P;
	ans += s[1];
	_for (i, 1, n - 1) {
		int j = i + 1, l1 = s[i].size(), l2 = s[j].size(), res = 0;
		_for (k, 1, l1)  hi[k] = (hi[k - 1] * base + (s[i][k - 1] - '0' + 1)) % P;
		_for (k, 1, l2)  hj[k] = (hj[k - 1] * base + (s[j][k - 1] - '0' + 1)) % P;
		_all (k, min(l1, l2), 1)  if (Hash(hi, l1 - k + 1, l1) == Hash(hj, 1, k)) { res = k; break; }
		ans += s[j].substr(res, l2 - res);
	}
	cout << ans << endl;
	return 0;
}
2023/3/14 22:18
加载中...