제출 #1230016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230016		mnnit_prakharg	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	61 ms	131072 KiB

necklace

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
#define pb push_back
#define ub upper_bound

void solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0, p1 = 0, p2 = 0;
    {
        int n1 = s1.size(), n2 = s2.size();
        int n = n1 + n2 + 1;
        vector<vector<int>> ha1(n, vector<int>(n));
        vector<vector<int>> ha3(n, vector<int>(n));
        {
            string s = s1 + "@" + s2;
            // prefix-function for matches from s1 to s2
            for (int i = 0; i < n1; i++)
            {
                ha1[i][i] = 0;
                int len = 0;
                for (int j = i + 1; j < n; j++)
                {
                    while (len && s[i + len] != s[j])
                        len = ha1[i][i + len - 1];
                    if (s[i + len] == s[j])
                        ha1[i][j] = ++len;
                    else
                        ha1[i][j] = 0;
                }
            }
            // Z-function for wrapping cases
            for (int i = 0; i < n1; i++)
            {
                ha3[i][i] = 0;
                int l = i, r = i;
                for (int j = i + 1; j < n; j++)
                {
                    int k = j - l;
                    if (j <= r && k < n && j + ha3[i][k] - 1 <= r)
                        ha3[i][j] = ha3[i][k];
                    else
                    {
                        int t = max(r, j);
                        while (t < n && s[t] == s[i + (t - j)])
                            t++;
                        ha3[i][j] = t - j;
                        l = j;
                        r = t - 1;
                    }
                }
            }
        }
        vector<vector<int>> ha2(n, vector<int>(n));
        {
            string s = s2 + "@" + s1;
            for (int i = 0; i < n2; i++)
            {
                ha2[i][i] = 0;
                int len = 0;
                for (int j = i + 1; j < n; j++)
                {
                    while (len && s[i + len] != s[j])
                        len = ha2[i][i + len - 1];
                    if (s[i + len] == s[j])
                        ha2[i][j] = ++len;
                    else
                        ha2[i][j] = 0;
                }
            }
        }
        // combine A and B across the cut
        for (int i = 1; i < n1; i++)
        {
            for (int j = 1; j < n2; j++)
            {
                int ma = ha1[i][n1 + j] + ha2[j][n2 + i];
                if (ma > ans)
                {
                    ans = ma;
                    p1 = i - ha2[j][n2 + i];
                    p2 = j - ha1[i][n1 + j];
                }
            }
        }
        // pure wrap-around matches (one piece spans the glue point)
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                int ma = ha3[i][(n1 + 1) + j];
                if (ma > ans)
                {
                    ans = ma;
                    p1 = i;
                    p2 = j;
                }
            }
        }
    }
    // handle reflection by reversing s2
    reverse(s2.begin(), s2.end());
    {
        int n1 = s1.size(), n2 = s2.size();
        int n = n1 + n2 + 1;
        vector<vector<int>> ha1(n, vector<int>(n));
        vector<vector<int>> ha3(n, vector<int>(n));
        {
            string s = s1 + "@" + s2;
            // prefix-function for matches from s1 to s2
            for (int i = 0; i < n1; i++)
            {
                ha1[i][i] = 0;
                int len = 0;
                for (int j = i + 1; j < n; j++)
                {
                    while (len && s[i + len] != s[j])
                        len = ha1[i][i + len - 1];
                    if (s[i + len] == s[j])
                        ha1[i][j] = ++len;
                    else
                        ha1[i][j] = 0;
                }
            }
            // Z-function for wrapping cases
            for (int i = 0; i < n1; i++)
            {
                ha3[i][i] = 0;
                int l = i, r = i;
                for (int j = i + 1; j < n; j++)
                {
                    int k = j - l;
                    if (j <= r && k < n && j + ha3[i][k] - 1 <= r)
                        ha3[i][j] = ha3[i][k];
                    else
                    {
                        int t = max(r, j);
                        while (t < n && s[t] == s[i + (t - j)])
                            t++;
                        ha3[i][j] = t - j;
                        l = j;
                        r = t - 1;
                    }
                }
            }
        }
        vector<vector<int>> ha2(n, vector<int>(n));
        {
            string s = s2 + "@" + s1;
            for (int i = 0; i < n2; i++)
            {
                ha2[i][i] = 0;
                int len = 0;
                for (int j = i + 1; j < n; j++)
                {
                    while (len && s[i + len] != s[j])
                        len = ha2[i][i + len - 1];
                    if (s[i + len] == s[j])
                        ha2[i][j] = ++len;
                    else
                        ha2[i][j] = 0;
                }
            }
        }
        // combine A and B across the cut
        for (int i = 1; i < n1; i++)
        {
            for (int j = 1; j < n2; j++)
            {
                int ma = ha1[i][n1 + j] + ha2[j][n2 + i];

                if (ma > ans)
                {
                    ans = ma;
                    p1 = i - ha2[j][n2 + i];
                    p2 = n2 - (j - 1 + ha2[j][n2 + i]) - 1;
                }
            }
        }
        // pure wrap-around matches (one piece spans the glue point)
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                int ma = ha3[i][(n1 + 1) + j];
                if (ma > ans)
                {
                    ans = ma;
                    p1 = i;
                    p2 = n2 - j - 1;
                }
            }
        }
    }
    cout << ans << "\n";
    cout << p1 << " " << p2 << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 0 / 15