제출 #251454

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

necklace

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 3005;

int kmp[N];
int fw[N];
int bw[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string S;   cin >> S;
    string T;   cin >> T;

    int n = sz(S);
    int m = sz(T);

    auto build = [&](int *f)    {
        kmp[0] = -1;

        for(int i = 1 ; i <= m ; ++i)   kmp[i] = 0;
        for(int i = 1 ; i <= n ; ++i)   f[i] = 0;

        for(int i = 2 ; i <= m ; ++i)
        for(int j = kmp[i - 1] ; j >= 0 ; j = kmp[j])
            if (T[i - 1] == T[j])   {
                kmp[i] = j + 1;
                break;
            }
        for(int i = 1 ; i <= n ; ++i)
        for(int j = f[i - 1] ; j >= 0 ; j = kmp[j])
            if (S[i - 1] == T[j])   {
                f[i] = j + 1;
                break;
            }
    };
    auto Solve = [&]()  {
        array<int,3>    ans = {0,0,0};

        for(int i = 1 ; i <= m ; ++i)   {
            build(fw);
            reverse(all(S));
            reverse(all(T));
            build(bw);
            reverse(all(S));
            reverse(all(T));
            reverse(bw + 1,bw + 1 + n);

            for(int j = 1 ; j <= n ; ++j)   {
                int len1 = min(fw[j],m - i + 1);
                int len2 = min(bw[j + 1],i - 1);

                if (ans[0] < len1 + len2)   {
                    ans[0] = len1 + len2;
                    ans[1] = j - len1;
                    ans[2] = i - len2 - 1;
                }
            }
            T = T.back() + T;
            T.pop_back();
        }
        return  ans;
    };
    auto ans1 = Solve();    reverse(all(T));
    auto ans2 = Solve();

    if (ans1[0] > ans2[0])  cout << ans1[0] << "\n" << ans1[1] << " " << ans1[2];
    else                    cout << ans2[0] << "\n" << ans2[1] << " " << m - ans2[2] - ans2[0];
}

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