제출 #1153615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153615		misavo	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	1 ms	320 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;
ll lps[3009];

void solve() {
    cin >> s1 >> s2;

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

    // f(i, 0, s1.size()) cout << lps[i] << " ";
    // cout<<endl;

    vector<vll> chars(27, vll());
    f(i, 0, s1.size()) chars[s1[i] - 'a'].pb(i);

    ll i1, i2, ans = 0;
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        ll curr = 0;
        while (j < s2.size() && r <= s1.size() && l >= 0) {
            if (r < s1.size() && s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll jj = j;
                        while (temp < l && jj < s2.size()) {
                            if (s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    temp = lps[temp - 1];
                                } while (temp && s1[temp] != s2[jj]);
                            }
                        }
                        if (temp == l && jj - i > ans) {
                            ans = jj - i;
                            i1 = chars[s2[j] - 'a'][back];
                            i2 = i;
                        }
                    } 
                }

                if (j - i > ans) {
                    ans = j - i;
                    i1 = l;
                    i2 = i;
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }  

        if (j - i > ans) {
            ans = j - i;
            i1 = l;
            i2 = i;
        }
    }

    reverse(all(s2));
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        ll curr = 0;
        while (j < s2.size() && r <= s1.size() && l >= 0) {
            if (r < s1.size() && s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll jj = j;
                        while (temp < l && jj < s2.size()) {
                            if (s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    temp = lps[temp - 1];
                                } while (temp && s1[temp] != s2[jj]);
                            }
                        }
                        if (temp == l && jj - i > ans) {
                            ans = jj - i;
                            i1 = chars[s2[j] - 'a'][back];
                            i2 = s2.size() - jj;
                        }
                    } 
                }
                
                if (j - i > ans) {
                    ans = j - i;
                    i1 = l;
                    i2 = s2.size() - j;
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }

        if (j - i > ans) {
            ans = j - i;
            i1 = l;
            i2 = s2.size() - j;
        }
    }
    cout << ans <<endl;
    cout << i1 << " " << i2 <<endl;
}

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

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

• Subtask 1: 0 / 15