최대 부분수열 (JUNGOL 4188)

https://jungol.co.kr/problem/4188

---

아이디어

주어진 수열을 문자열이라고 생각해봅시다. 그리고 접미사배열과 LCP 배열을 만들어줍시다.

 

그러면 LCP배열 상에서 크기가 K-1인 구간을 잡고 그 구간 내에서의 LCP 값의 최솟값을 L이라 하면, 그 구간에서는 길이가 L인 부분문자열이 K개 존재한다는것을 의미합니다. 그러므로 LCP배열을 잡고 임의의 크기가 K-1인 구간에 대해서 LCP값의 최솟값중 최댓값을 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#define ll long long
using namespace std;

ll N;
vector <ll> GetPi(vector <ll> arr)
{
    vector <ll> Pi(N);

    ll idx=0;
    for (ll i=1;i<N;i++)
    {
        while (idx && arr[idx]!=arr[i]) idx=Pi[idx-1];
        if (arr[idx]==arr[i]) Pi[idx]=++idx;
    }

    return Pi;
}

ll Sz;
vector <ll> num;

bool cmp(ll i,ll j) //i<j를 판별
{
    if (num[i]!=num[j]) return num[i]<num[j];
    if (i+Sz>=N) return true;
    if (j+Sz>=N) return false;
    return num[i+Sz]<num[j+Sz];
}

vector <ll> GetSuffix(vector <ll> arr)
{
    vector <ll> Pi=GetPi(arr),perm;
    num.resize(N);

    for (ll i=0;i<N;i++) perm.push_back(i);
    for (ll i=0;i<N;i++) num[i]=arr[i];

    Sz=1;
    while (Sz<N)
    {
        sort(perm.begin(),perm.end(),cmp);

        ll cnt=0;
        vector <ll> NewNum(N);
        for (ll i=1;i<N;i++)
        {
            if (cmp(perm[i-1],perm[i])) cnt++;
            NewNum[perm[i]]=cnt;
        }
        num=NewNum;

        Sz*=2;
    }

    return perm;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll K,i,x;
    vector <ll> arr;

    cin>>N>>K;
    for (i=0;i<N;i++)
    {
        cin>>x;
        arr.push_back(x);
    }

    vector <ll> sa=GetSuffix(arr),isa(N);

    for (ll i=0;i<N;i++) isa[sa[i]]=i;
    
    vector <ll> LCP(N);
    ll now=0;
    for (ll i=0;i<N;i++)
    {
        if (isa[i]==0) continue;
        while (i+now<N && sa[isa[i]-1]+now<N && arr[i+now]==arr[sa[isa[i]-1]+now])
            now++;
        LCP[i]=now--;
        if (now<0) now++;
    }
    
    ll res=0;
    deque <pair <ll,ll> > dq;
    for (ll i=1;i<N;i++)
    {
        if (dq.size() && dq.front().second==i-K+1) dq.pop_front();
        while (dq.size() && dq.back().first>=LCP[sa[i]]) dq.pop_back();
        dq.push_back({LCP[sa[i]],i});

        if (i>=K-1) res=max(res,dq.front().first);
    }

    cout<<res;
}