oj.uz

답안 #469285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469285 2021-08-31T10:54:18 Z noob_c0de Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 349 ms 580 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 432 KB Output is correct
2 Correct 293 ms 452 KB Output is correct
3 Correct 349 ms 460 KB Output is correct
4 Correct 274 ms 440 KB Output is correct
5 Correct 215 ms 460 KB Output is correct
6 Correct 231 ms 440 KB Output is correct
7 Correct 261 ms 452 KB Output is correct
8 Correct 283 ms 580 KB Output is correct
9 Correct 306 ms 436 KB Output is correct