mxqz,hash写法tle on #3
查看原帖
mxqz,hash写法tle on #3
761491
Zzzcr楼主2023/12/23 17:45
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define _f(i, a, b) for (int i = a; i <= b; ++i)
#define _d(i, a, b) for (int i = a; i >= b; --i)
using pii = pair<int, int>;
using ll = long long;
#define fi first
#define se second

static constexpr int N = 1e6 + 5, mod = 1e9 + 7, mod2 = 1e9 + 9;

int n, pw1[N], inv1[N], pw2[N], inv2[N], len, hs1[N], hs2[N], lt;

int vs1[N], vs2[N], base;

string s, t;

int ksm(int x, int t, int p) {
	int ret = 1;
	while(t) {
		if(t & 1) ret = 1ll * ret * x % p;
		x = 1ll * x * x % p, t >>= 1;
	} return ret;
}

bool check(int x) {
	ll v1 = (hs1[len] - hs1[len - x] + mod) % mod;
	v1 = 1ll * v1 * inv1[len - x] % mod;
	if(v1 != vs1[x]) return 0;
	v1 = (hs2[len] - hs2[len - x] + mod2) % mod2;
	v1 = 1ll * v1 * inv2[len - x] % mod2;
	return (v1 == vs2[x]);
}

void calc(int pos, int h1[], int h2[], string str) {
	h1[pos] = (h1[pos - 1] + 1ll * str[pos] * pw1[pos] % mod) % mod,
	h2[pos] = (h2[pos - 1] + 1ll * str[pos] * pw2[pos] % mod2) % mod2;
}

void solve() {
	srand(time(0)), base = rand() % 233 + 131;
	cin >> n, pw1[0] = pw2[0] = 1, pw1[1] = pw2[1] = base;
	inv1[1] = ksm(base, mod - 2, mod), inv2[1] = ksm(base, mod2 - 2, mod2);
	_f(i, 2, N - 5) {
		pw1[i] = 1ll * pw1[i - 1] * base % mod, pw2[i] = 1ll * pw2[i - 1] * base % mod2;
		inv1[i] = 1ll * inv1[i - 1] * inv1[1] % mod, inv2[i] = 1ll * inv2[i - 1] * inv2[1] % mod2;
	}
	cin >> s, len = s.length(), s = '$' + s;
	_f(i, 1, len) calc(i, hs1, hs2, s);
	_f(i, 2, n) {
		cin >> t, lt = t.length(); t = '#' + t;
		_f(i, 1, lt) calc(i, vs1, vs2, t);
		int ans = 0;
		_d(i, min(lt, len), 1) if(check(i)) {
			ans = i; break;
		}
		s += t.substr(ans + 1, lt - ans);
		_f(i, len + 1, len + lt - ans) calc(i, hs1, hs2, s);
		len = len + lt - ans;
	}
	_f(i, 1, len) cout << s[i];
	return ;
}

signed main() {

	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	solve();
	return 0;
}

// powered by zzzcr.

2023/12/23 17:45
加载中...