제출 #1335991

#제출 시각아이디문제언어결과실행 시간메모리
1335991lanternerNecklace (Subtask 4) (BOI19_necklace4)C++20
15 / 15
260 ms588 KiB
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
#define iii int, int ,int
#define tp tuple

using namespace std;

// FIX 1: Tăng kích thước mảng an toàn để không bị tràn khi n, m lớn.
const ll maxN = 15005; 

string s, t;
int n, m, pi[maxN][2];

void kmp (string s, int side) {
	int len = s.size()-1;
	fto (i, 1, len, 1) {
		int j = pi[i-1][side];
		while (0 < j && s[i] != s[j]) j = pi[j - 1][side];
		if (s[i] == s[j]) j++;
		pi[i][side] = j;
	}
}

tp<iii> solve(string s, string t, int side) {
	n = s.size()-1, m = t.size()-1;
	tp<iii> ans = make_tuple(-1, 1, 1); // Khởi tạo với giá trị nhỏ để rớt vào điều kiện cập nhật
	reverse(all(t));
	string rev = t;
	reverse(all(t));	
	
	fto (i, 0, n, 1) {
		string s1 = s.substr(0, i+1), s2 = s.substr(i+1, n - i);
		reverse(all(s1));
		int n1 = s1.size(), n2 = s2.size();
		s1 = s1 + "#" + rev;
		s2 = s2 + "#" + t;
		kmp(s1, 0); 
		kmp(s2, 1);
		
		fto (j, -1, m, 1) {
			int L1 = pi[n1+m-j][0];
			int L2 = pi[n2+1+j][1];
			
			int len = L1 + L2;
			int pos_s = i - L1 + 1;
			// FIX 2: Sửa lại công thức `m - (j + L1)` khi side == 0
			int pos_t = side ? (j - L2 + 1) : (m - (j + L1));
			
			// FIX 3: Lưu pos_s và pos_t bằng giá trị ÂM
			// Để hàm max() chọn ưu tiên vị trí nhỏ nhất khi xảy ra trường hợp bằng độ dài (len)
			ans = max(ans, make_tuple(len, pos_s, pos_t));
		}
	}
	return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    if (!(cin >> s >> t)) return 0;
    
    tp<iii> ans = solve(s, t, 1);
    reverse(all(t));
    ans = max(ans, solve(s, t, 0));
    
    // Khi in ra, nhớ thêm dấu trừ (-) để đưa giá trị vị trí về lại số dương
    cout << get<0>(ans) << '\n';
    cout << get<1>(ans) << ' ' << get<2>(ans) << '\n';
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...