제출 #1276947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276947		Thunnus	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	0 ms	332 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define  vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()                      

inline void solve(){
    string s, t;
    cin >> s >> t;

    bool reversed = false;
    vi lps1(max(sz(s), sz(t)) + 1), lps2(max(sz(s), sz(t)) + 1);
    auto kmp = [&](string s, vi &lps) -> void {
        for(int i = 1; i < sz(s); i++){
            int len = lps[i - 1];
            while(len > 0 && s[i] != s[len]){
                len = lps[len - 1];
            }
            if(s[i] == s[len]){
                len++;
            }
            lps[i] = len;
        }
        return;
    };

    auto calc = [&](string s, string t) -> array<int, 3> {
        int n = sz(s), m = sz(t);
        array<int, 3> ans = {0, 0, 0};
        for(int i = 0; i < n; i++){
            string s1 = s.substr(0, i), s2 = s.substr(i, n - i), t1 = t, t2 = t;
            reverse(s1.begin(), s1.end()), reverse(t2.begin(), t2.end());
            kmp(s1 + '#' + t1, lps1), kmp(s2 + '#' + t2, lps2);
            for(int j = 1; j <= m; j++){
                ans = max(ans, array<int, 3>{lps1[i + j] + lps2[n - i + m - j], i - lps1[i + j], reversed ? m - j - lps2[n - i + m - j] : j - lps1[i + j]});
            }
        }
        return ans;
    };
    array<int, 3> ans = calc(s, t);
    reverse(t.begin(), t.end());
    reversed = true;
    ans = max(ans, calc(s, t));
    cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n";
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40