oj.uz

답안 #754806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754806 2023-06-08T15:46:02 Z adaawf Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 329 ms 524 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kmp(string s) {
	int n = s.size();
	vector<int> k(n);
	for (int i = 1; i < n; i++) {
		int j = k[i - 1];
		while (j != 0 && s[i] != s[j]) {
            j = k[j - 1];
		}
		if (s[i] == s[j]) {
            j++;
		}
		k[i] = j;
	}
	return k;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size(), ma = 0;
	pair<int, int> p;
	for (int i = 0; i < n; i++) {
		string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
		reverse(h.begin(), h.end());
		reverse(g.begin(), g.end());
		vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
		for (int j = 1; j <= m; j++) {
			int h = v[i + j] + vv[n + m - i - j];
			if (ma < h) {
				ma = h;
				p = {i - v[i + j], j - v[i + j]};
			}
		}
	}
	reverse(t.begin(), t.end());
	for (int i = 0; i < n; i++) {
		string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
		reverse(h.begin(), h.end());
		reverse(g.begin(), g.end());
		vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
		for (int j = 1; j <= m; j++) {
			int h = v[i + j] + vv[n + m - i - j];
			if (ma < h) {
				ma = h;
				p = {i - v[i + j], m - j - vv[n + m - i - j]};
			}
		}
	}
	cout << ma << endl;
	cout << p.first << ' ' << p.second;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 444 KB Output is correct
2 Correct 232 ms 444 KB Output is correct
3 Correct 329 ms 440 KB Output is correct
4 Correct 230 ms 324 KB Output is correct
5 Correct 132 ms 340 KB Output is correct
6 Correct 145 ms 436 KB Output is correct
7 Correct 205 ms 524 KB Output is correct
8 Correct 235 ms 396 KB Output is correct
9 Correct 249 ms 444 KB Output is correct