Submission #1098718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098718	2024-10-09T19:10:59 Z	shahd_abbara	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	509 ms	636 KB

necklace

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define what(x) cout << (#x) << " -> " << x << '\n';
#define cno cout << "NO" \
                 << "\n"
#define cy cout << "YES" \
                << "\n"
#define c1 cout << "-1" << '\n'
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);

const ll N = 1000005;
const ll mod = 1000000007;
ll n, m, x, y, z, l, r, d, q, mn, sum, temp;
ll a[N];
vector<int> prefix_function(string s, int start)
{
    int n = (int)s.length();
    vector<int> pi(n), ans;

    for (int i = 1; i < n; i++)
    {

        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    for (int i = start; i < n; i++)
        ans.pb(pi[i]);

    return ans;
}

vector<int> suffix_function(string s, int start)
{
    int n = (int)s.length();
    vector<int> pi(n), ans;

    for (int i = 1; i < n; i++)
    {

        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    for (int i = start; i < n; i++)
        ans.pb(pi[i]);
    reverse(ans.begin(), ans.end());
    return ans;
}
pair<int, pair<int, int>> mx;
void solve(string s, string t, bool rev)
{
    string te;

    n = s.sz;
    m = t.sz;
    s += s;
    t += t;
    te = t;
    reverse(te.begin(), te.end());
    pair<int, int> ans{-1, -1};
    vector<int> z, p;

    for (int i = 0; i < n; i++)
    {
        // what(i);
        string r = s.substr(i, n), f;
        f = r;
        r += '#';
        r += t;

        reverse(f.begin(), f.end());
        f += '#';
        f += te;
        //  cout << r << ' ' << f << endl;
        z = suffix_function(f, n + 1), p = prefix_function(r, n + 1);

        for (int j = 0; j < m; j++)
        {
            // what(n - (i + p[j] - 1) - 1)
            //  what(p[j])
            //   what(((rev) ? n - (i + p[j] - 1) - 1 : i - z[j + 1]));
            if (p[j])
                mx = max(make_pair(min(p[j] + z[j + 1], int(m)), make_pair(int((rev) ? n - (i + p[j] - 1) - 1 : i - z[j + 1]), j - p[j] + 1)), mx);
            //    cout << p[i] << ' ' << z[i + 1] << endl;
        }
    }
}
int main()
{
    IOS int testcases = 1;

    // cin >> testcases;
    while (testcases--)
    {
        string s, t;
        string se, te;
        cin >> s >> t;
        n = s.sz;
        m = t.sz;

        se = s;
        te = t;
        reverse(se.begin(), se.end());

        solve(se, te, 1), solve(s, t, 0);
        cout << mx.ff << endl;
        cout << mx.ss.ff << ' ' << mx.ss.ss << endl;
    }
}

Subtask #1

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	481 ms	600 KB	Output is correct
2	Correct	395 ms	636 KB	Output is correct
3	Incorrect	509 ms	600 KB	Output isn't correct
4	Halted	0 ms	0 KB	-