제출 #1154504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154504		misavo	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	141 ms	612 KiB

necklace

#include <bits/stdc++.h>
// #include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x <<  <<endl;
#define printp(a) for(auto x : a) cout << x.first <<  << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, k, a, b, tot;
string s1, s2;

void aux(bool rev) {
    f(i, 0, s1.size()) {
        vll temp(s1.size() - i);
        temp[0] = 0;
        ll l = 0, r = 0;
        f(j, 1, temp.size()) {
            if (j < r) temp[j] = min(r - j, temp[j - l]);
            while (j + temp[j] < temp.size() && s1[i + temp[j]] == s1[i + j + temp[j]]) temp[j]++;
            if (j + temp[j] > r) {
                l = j;
                r = j + temp[j];
            }
        }

        vll z(n);
        l = 0; r = 0;
        f(j, 0, n) {
            if (j < r) z[j] = min(r - j, temp[j - l]);
            while (i + z[j] < s1.size() && j + z[j] < n && s1[i + z[j]] == s2[j + z[j]]) z[j]++;
            if (j + z[j] > r) {
                l = j;
                r = j + z[j];
            }
        }

        ll mx = 0;
        f(j, 0, n) mx = max(mx, z[j]);
        if (!mx) continue;

        vll kmp(s1.size() - i - mx + 1);
        kmp[0] = 0;
        f(j, 1, s1.size() - i - mx) {
            ll len = kmp[j-1];
            while (len && s1[len + i + mx] != s1[j]) len = kmp[len-1];
            if (s1[j] == s1[len + i + mx]) len++;
            kmp[j] = len;
        }

        vll lps(n+1);
        lps[0] = 0;
        ll len = 0;
        cf(j, 1, n) {
            if (len+i+mx < s1.size() && s1[i+mx+len] == s2[j-1]) len++;
            else {
                if (len > 0) {
                    do {
                        len = kmp[len-1];
                    } while (len > 0 && s1[len+i+mx] != s2[j-1]);
                    if (len+i+mx < s1.size() && s1[len+i+mx] == s2[j-1]) len++;
                }
            } lps[j] = len;
        }

        f(j, 0, n) {
            if (z[j] == mx) {
                ll curr = mx + lps[j];
                if (curr > tot) {
                    tot = curr;
                    a = i;
                    if (rev) b = n - (j + mx); 
                    else b = j - lps[j];
                }
            }
        }
    }
}

void solve() {
    cin >> s1 >> s2;
    n = s2.size();

    aux(0);
    reverse(all(s2));
    aux(1);
    cout << tot <<endl;
    cout << a << " " << b <<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    t = 1;
    while (t--) {
        solve();
    }
}

• Subtask 1: 15 / 15