Submission #1099967

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099967	2024-10-12T09:29:20 Z	andrei_iorgulescu	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	380 ms	484 KB

necklace

#include <bits/stdc++.h>

using namespace std;

int n, m;
string aaa, bbb;
char a[3005], b[3005];

struct sol
{
    int lungime = 0, p1 = 0, p2 = 0;
};

int k;
char s[6005], revs[6005];
int kmp[6005], revkmp[6005];///kmp[i] = cel mai lung prefix al lui s care e sufix al lui s[1...i], de lungime strict sub i

void build_kmps()
{
    memset(kmp, 0, sizeof(kmp));
    memset(revkmp, 0, sizeof(revkmp));
    kmp[1] = 0;
    for (int i = 2; i <= k; i++)
    {
        kmp[i] = kmp[i - 1];
        while (kmp[i] != 0 and s[i] != s[kmp[i] + 1])
            kmp[i] = kmp[kmp[i]];
        if (s[i] == s[kmp[i] + 1])
            kmp[i]++;
    }
    revkmp[1] = 0;
    for (int i = 2; i <= k; i++)
    {
        revkmp[i] = revkmp[i - 1];
        while (revkmp[i] != 0 and revs[i] != revs[revkmp[i] + 1])
            revkmp[i] = revkmp[revkmp[i]];
        if (revs[i] == revs[revkmp[i] + 1])
            revkmp[i]++;
    }
}

sol solve()
{
    sol ans;
    ans.lungime = 0;
    for (int p1 = 1; p1 <= n + 1; p1++)
    {
        k = 0;
        for (int i = p1; i <= n; i++)
            s[++k] = a[i];
        s[++k] = '$';
        for (int i = 1; i <= m; i++)
            s[++k] = b[i];
        s[++k] = '%';
        for (int i = 1; i < p1; i++)
            s[++k] = a[i];
        for (int i = 1; i <= k; i++)
            revs[i] = s[k + 1 - i];
        build_kmps();
        for (int p2 = 1; p2 <= m + 1; p2++)
        {
            int l1 = kmp[n - p1 + p2 + 1];
            int l2 = revkmp[m - p2 + p1 + 1];
            sol cur;
            cur.lungime = l1 + l2;
            cur.p1 = p1 - l2;
            cur.p2 = p2 - l1;
            if (cur.lungime > ans.lungime)
                ans = cur;
        }
    }
    return ans;
}

int main()
{
    cin >> aaa >> bbb;
    n = aaa.size();
    m = bbb.size();
    for (int i = 1; i <= n; i++)
        a[i] = aaa[i - 1];
    for (int i = 1; i <= m; i++)
        b[i] = bbb[i - 1];
    sol sol1 = solve();
    reverse(b + 1, b + m + 1);
    sol sol2 = solve();
    sol2.p2 = m + 1 - (sol2.p2 + sol2.lungime - 1);
    if (sol2.lungime > sol1.lungime)
        swap(sol1, sol2);
    cout << sol1.lungime << '\n' << sol1.p1 - 1 << ' ' << sol1.p2 - 1;
    return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	331 ms	344 KB	Output is correct
2	Correct	284 ms	344 KB	Output is correct
3	Correct	380 ms	344 KB	Output is correct
4	Correct	303 ms	344 KB	Output is correct
5	Correct	201 ms	348 KB	Output is correct
6	Correct	213 ms	348 KB	Output is correct
7	Correct	291 ms	348 KB	Output is correct
8	Correct	297 ms	484 KB	Output is correct
9	Correct	305 ms	480 KB	Output is correct