Submission #1196844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196844		zyadhany	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	180 ms	131072 KiB

necklace

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<long long>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;

const int MODE = 1e9+7;

vector<int> BuildLPS(deque<char> &s) {
    int n = s.size();
    vector<int> LPS(n, 0);

    for (int i = 1; i < n; i++)
    {
        int j = LPS[i - 1];
        while (j && s[i] != s[j])
            j = LPS[j - 1];
        LPS[i] = j + (s[j] == s[i]);
    }
    
    return (LPS);
}


vii req(string &s, string &t) {
    deque<char> X;
    X.push_back('#');
    for (auto a : t) X.push_back(a);

    vii dp(s.size(), vi(t.size()));
    for (int i = s.size() - 1; i >= 0; i--)
    {
        X.push_front(s[i]);
        auto pi = BuildLPS(X);
        for (int j = s.size()-i+1, h = 0; j < pi.size(); j++, h++)
        {
            dp[i][h] = pi[j];   
        }
    }
    
    return dp;
}

vi sol(string s, string t) {
    ll n = s.size(), m = t.size();

    vii dp1 = req(s, t);
    vii dp2 = req(t, s);
    vi res(3);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (s[i] == t[j]) {
                res = {1, i, j};
            }
        }
    }
    
    for (int i = 0; i < n-1; i++)
    {
        for (int j = 0; j < m-1; j++)
        {
            ll a = dp1[i+1][j];
            ll b = dp2[j+1][i];
            vi re = {a+b, i+1-b, j+1-a};
            res = max(res, re);
        }
    }

    return res;
}

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

    auto re = sol(s, t);
    reverse(all(t));
    auto re2 = sol(s, t);

    if (re2>re) {
        re = re2;
        re[2] = t.size()-1-re[2];
    }

    cout << re[0] << '\n';
    cout << re[1] << ' ' << re[2] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;
 
    // freopen("dec.in", "r", stdin);
    // freopen("dec.out", "w", stdout);

    // cin >> size;
    for (int i = 1; i <= size; i++)
        solve(i);
}

• Subtask 1: 0 / 15