BOJ 17187 - Necklace (P1), BOJ 22195 - Necklace 4 (D5)

둘은 메모리 제한만 다른 문제이다.

 

사용 알고리즘

kmp

 

풀이

두 문자열을 s, t라 하자. 뒤집는 경우는 s든 t든 하나만 뒤집고 똑같이 하면 되니 뒤집는 경우는 고려하지 않아도 된다.

t = A+B로 쪼개고 r = B + '$' + s + '#' + A 꼴로 된 문자열을 생각해보자. 중간에 $와 #는 문자열을 구분짓기 위한 dummy이다.

예를 들어, s = "yxbadctz", t = "dcbayxz"일 때 A = "dc", B = "bayxz"가 가능하다.

r = "baxyz$yxbadctz#dc"가 된다. 이제 여기서 r의 fail function과 rev(r)의 fail function을 구한 다음 $와 # 사이에 있는 인덱스 i를 순회하면서 fail_r{i} + fail_rev(r){|r|-2-i}의 최댓값을 구하면 된다. 위의 r에서는 i가 [baxyz$yxba]{dctz#dc}일 때 (']'와 '{' 사이에 i가 있다고 생각하면 된다)가 최대이다.

 

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define sz(x) (ll)x.size()
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> PP;
const ll inf = 2e18;
string s, t;
ll n, m;
int main(){
    fast;
    cin>>s>>t; n = sz(s), m = sz(t);
    string r = t + "#" + s + "$";
    string rt = r; reverse(all(rt));
    ll ans=0, p1=-1, p2=-1;
    //안뒤집기
    for(int k = 0 ; k <= m ; k++){
        vector<ll> pi(sz(r)), pi2(sz(r));
        for(int i = 1, j = 0 ; i < sz(r) ; i++){
            while(j>0 and r[i] ^ r[j])j = pi[j-1];
            if(r[i] == r[j])pi[i] = ++j;
        }
        for(int i = 1, j = 0 ; i < sz(rt) ; i++){
            while(j>0 and rt[i] ^ rt[j])j = pi2[j-1];
            if(rt[i] == rt[j])pi2[i] = ++j;
        }
        for(int i = m-k+1 ; i-(m-k+1) <= n ; i++){
            ll x = pi[i-1] + pi2[sz(r)-2-(i-1)];
            if(x>ans){
                ans=x;
                p1 = i-(m-k+1)-pi[i-1];
                p2 = k-pi2[sz(r)-2-(i-1)];
            }
        }
        r += r[0]; r.erase(r.begin());
        rt.insert(rt.begin(),rt.back()); rt.pop_back();
    }
    reverse(all(t));
    r = t + "#" + s + "$";
    rt = r; reverse(all(rt));
    //뒤집기
    for(int k = 0 ; k <= m ; k++){
        vector<ll> pi(sz(r)), pi2(sz(r));
        for(int i = 1, j = 0 ; i < sz(r) ; i++){
            while(j>0 and r[i] ^ r[j])j = pi[j-1];
            if(r[i] == r[j])pi[i] = ++j;
        }
        for(int i = 1, j = 0 ; i < sz(rt) ; i++){
            while(j>0 and rt[i] ^ rt[j])j = pi2[j-1];
            if(rt[i] == rt[j])pi2[i] = ++j;
        }
        for(int i = m-k+1 ; i-(m-k+1) <= n ; i++){
            ll x = pi[i-1] + pi2[sz(r)-2-(i-1)];
            if(x>ans){
                ans=x;
                p1 = i-(m-k+1)-pi[i-1];
                p2 = m-1 - (k-pi2[sz(r)-2-(i-1)]) - (x-1);
            }
        }
        r += r[0]; r.erase(r.begin());
        rt.insert(rt.begin(),rt.back()); rt.pop_back();
    }
    cout<<ans<<endl<<p1<<" "<<p2;
}