제출 #1165800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165800		cpismylifeOwO	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	243 ms	536 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 6e3 + 5;

int n, m;
string a, b;

void Inp()
{
    cin >> a >> b;
    n = (int)a.length();
    m = (int)b.length();
}

int Pre[MaxN];
string sam;
int Z[MaxN];

void Zfunc()
{
    int k = (int)sam.length();
    Z[0] = 0;
    int l = 0, r = 0;
    for (int x = 1; x < k; x++)
    {
        Z[x] = 0;
        if (x <= r)
        {
            Z[x] = min(Z[x - l], r - x + 1);
        }
        while (x + Z[x] < k && sam[x + Z[x]] == sam[Z[x]])
        {
            Z[x]++;
        }
        if (x + Z[x] - 1 > r)
        {
            l = x;
            r = x + Z[x] - 1;
        }
    }
}

int mx[MaxN];
int mi[MaxN];

pair<int, pair<int, int>> Calc()
{
    pair<int, pair<int, int>> res = make_pair(0, make_pair(0, 0));
    int tmp = n;
    sam = a;
    sam.push_back('#');
    sam += b;
    Zfunc();
    for (int x = 0; x <= m; x++)
    {
        Pre[x] = 0;
    }
    for (int x = 0; x <= n; x++)
    {
        deque<int> dq;
        mi[0] = 1;
        for (int y = 1; y <= m; y++)
        {
            if (Z[tmp + y] > 0)
            {
                dq.push_back(y);
            }
            while (!dq.empty() && Z[tmp + dq.front()] + dq.front() - 1 < y)
            {
                dq.pop_front();
            }
            if (dq.empty())
            {
                mi[y] = y + 1;
            }
            else
            {
                mi[y] = dq.front();
            }
        }
        while (!dq.empty())
        {
            dq.pop_back();
        }
        mx[m + 1] = m;
        for (int y = m; y > 0; y--)
        {
            if (Pre[y] > 0)
            {
                dq.push_back(y);
            }
            while (!dq.empty() && dq.front() - Pre[dq.front()] + 1 > y)
            {
                dq.pop_front();
            }
            if (dq.empty())
            {
                mx[y] = y - 1;
            }
            else
            {
                mx[y] = dq.front();
            }
        }
        for (int y = 0; y <= m; y++)
        {
            res = max(res, make_pair(mx[y + 1] - mi[y] + 1, make_pair(x - (mx[y + 1] - y) + 1, mi[y])));
            //if (mx[y + 1] - mi[y] + 1 == 4) cout << x << " " << y << " " << mx[y + 1] << " " << mi[y] << " " << res.second.second << "\n";
        }
        for (int y = m; y > 0; y--)
        {
            if (a[x] == b[y - 1])
            {
                Pre[y] = Pre[y - 1] + 1;
            }
            else
            {
                Pre[y] = 0;
            }
        }
        reverse(sam.begin(), sam.end());
        sam.pop_back();
        reverse(sam.begin(), sam.end());
        tmp--;
        Zfunc();
    }
    return res;
}

void Exc()
{
    pair<int, pair<int, int>> res = Calc();
    //cout << res.first << "\n" << res.second.first - 1 << " " << res.second.second - 1;
    reverse(b.begin(), b.end());
    pair<int, pair<int, int>> restmp = Calc();
    restmp.second.second = m - restmp.second.second + 1;
    restmp.second.second -= restmp.first - 1;
    res = max(res, restmp);
    cout << res.first << "\n" << res.second.first - 1 << " " << res.second.second - 1;
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 15 / 15