Submission #1098704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098704		shahd_abbara	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	467 ms	604 KiB

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, mx, 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;
}
int solve(string s, string t)
{
    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;
    int mx = 0;
    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 i = 0; i < m; i++)
        {

            mx = max(min(p[i] + z[i + 1], int(m)), mx);
            //   cout << p[i] << ' ' << z[i + 1] << endl;
        }
    }

    return mx;
}
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());

        cout << max(solve(se, te), solve(s, t));
    }
}

• Subtask 1: 0 / 15