Submission #469285

#	Time	Username	Problem	Language	Result	Execution time	Memory
469285		noob_c0de	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	349 ms	580 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define sz(x) (int)x.size()
#define ar array
vector<int> kmp(string st)
{
    int n = sz(st);
    vector<int> f(n);
    for (int i = 1; i < n; i++)
    {
        int j = f[i - 1];
        while(j && st[j] != st[i]) j = f[j - 1];
        if (st[j] == st[i]) j++;
        f[i] = j;
    }
    return f;
}
string a, b;
ar<int, 3> ans;
/*  zxyabcd 7
    yxbadctz 8
    ztcdabxy
    yxz*yxbadctz
    abcd*ztcdabxy
*/
void solve(bool isrev)
{
    int m = sz(a);
    int n = sz(b);
    string revb = "";
    for (int i = n - 1; i >= 0; i--) revb.push_back(b[i]);
    for (int i = 0; i < m; i++)
    {
        string s1 = a.substr(0, i), s2 = a.substr(i, m - i);
        reverse(s1.begin(), s1.end());
        vector<int> p1 = kmp(s1 + '*' + b), p2 = kmp(s2 + '*' + revb);
        // cout << s1 + '*' + b << ' ' << s2 + '*' + revb << '\n';
        for (int j = 1; j <= n; j++)
        {
            int l1 = i - p1[i + j], l2;
            if (!isrev) l2 = j - p1[i + j];
            else l2 = n - j - p2[m - i + n - j];
            ans = max(ans, {p1[i + j] + p2[m - i + n - j], l1, l2});
            // if (i == 3) cout << p1[i + j] + p2[m - i + n - j] << '\n';
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> b;
    solve(0);
    reverse(b.begin(), b.end());
    solve(1);
    cout << ans[0] << '\n' << ans[1] << ' ' << ans[2];  
    return 0;
}

• Subtask 1: 15 / 15