Submission #667173

#	Time	Username	Problem	Language	Result	Execution time	Memory
667173		Kahou	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	1584 ms	324 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int M = 1e9 + 9;
const int B = 1854;
int add(int a, int b) {
	a += b;
	if (a >= M) a -= M;
	if (a < 0) a += M;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%M;
}

const int N = 105;

int n, m, h[N], h1[N], h2[N], pw[N];
string s, t;

int H(int l, int r) {
	return add(h[r], -mul(h[l], pw[r-l]));
}
int H1(int l, int r) {
	return add(h1[r], -mul(h1[l], pw[r-l]));
}
int H2(int l, int r) {
	return add(h2[l], -mul(h2[r], pw[r-l]));
}

void solve() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
	pw[0] = 1;
	for (int i = 1; i < N; i++) {
		pw[i] = mul(pw[i-1], B);
	}
	for (int i = 1; i <= n; i++) {
		h[i] = add(mul(h[i-1], B), s[i]);
	}
	for (int i = 1; i <= m; i++) {
		h1[i] = add(mul(h1[i-1], B), t[i]);
	}
	for (int i = m-1; i >= 0; i--) {
		h2[i] = add(mul(h2[i+1], B), t[i]);
	}
	int ans = 0;
	for (int l1 = 0; l1 < n; l1++) {
		for (int r1 = l1+1; r1 <= n; r1++) {
			int len = r1-l1;
			int tmp = H(l1, r1);
			for (int l2 = 0; l2 <= m-len; l2++) {
				int r2 = l2 + len;
				for (int p = l2; p < r2; p++) {
					int tmp1 = add(H1(l2, p), mul(H1(p, r2), pw[p-l2]));
					int tmp2 = add(H2(p, r2), mul(H2(l2, p), pw[r2-p]));
					if (tmp == tmp1 || tmp == tmp2) {
						ans = max(ans, len);
					}
				}
			}
		}
	}
	cout << ans << endl;

}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

• Subtask 1: 0 / 15