ACM-ICPC 2022 Seoul Regional H

미러에서 풀었어야 했는데 괜히 능지 더 쓰려다가 못 풀었다. 3시간 째 실제 대회에서 푼 사람이 안 나오길래 엄청 어려운 줄... 

그래도 문자열 문제 어떻게 푸는지 기억이 아예 사라진 것은 아니어서 조금 신기했다. 가뭄에 콩 나듯 하는 PS....

 

Suffix Array + LCP를 만들자. 여기서 만약에 $$\max(lcp_{i-1}, lcp_{j+1}) < \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$가 성립한다면, $i-1$번째 substring 부터 $j$번째 substring까지 총 $j-i+2$개의 substring이 $$\min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$ 길이의 common prefix를 가지며, 특히 $$[\max(lcp_{i-1}, lcp_{j+1}) + 1, \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)]$$ 구간에 속하는 길이의 prefix 들은 정확히 $j-i+2$번 등장하게 된다. 즉, 이들은 $f(j-i+2)$에 들어가는 후보군이라고 볼 수 있다. 

 

그래서 일단 저런 경우들을 모두 관리해야 하는데, 이건 stack을 써서 할 수 있다. 대충 $st$번째 문자열부터 $en$번째 문자열까지 common prefix가 $l$이라는 것을 하나의 struct로, 즉 $(st, en, l)$ 형태로 관리한다고 치자. 그러면 $lcp_i$를 보면서 얻는 것은 $(i-1, i, lcp_i)$라는 struct다.

 

이제 stack을 머리속으로 그리면서 생각을 해보자. 스택의 top을 $S$라고 생각을 하고, 지금 $(i-1, i, lcp_i)$를 본다고 하자.

• $S_l > lcp_i$인 경우를 생각해보면, 현재 [$S$ 이전의 원소인 $T$], [$S$], [$(i-1, i, lcp_i)$]가 순서대로 stack에 대기중이다.
  • stack 상 invariant를 하나 유지하자. 이제부터 stack에 쌓인 순서대로 $l$ 값이 증가하도록 한다. 자연스러운 생각이다.
  • 그러면 $S_l > \max(T_l, lcp_i)$이므로, 여기서 $f$ 값을 update 할 케이스가 발생한다. 
  • 즉, $[\max(T_l, lcp_i) + 1, S_l]$ 구간에 속하는 prefix들은 정확히 $S_{en} - S_{st} + 1$번 등장하게 된다. 
  • 이제 $f$를 계산하려면 disjoint occurrence 횟수를 계산해야 한다. 
    • 이는 $S$에 대응되는 suffix array 값들을 set으로 관리하고, naive 하게 lower bound를 사용하면서 계산하면 된다.
    • 결국 "최대 occurrence를 유지하는 최대 길이"를 계산해야 하는데, 이는 $[\max(T_l, lcp_i) + 1, S_l]$에서 이분탐색을 하면 된다.
  • 이제 다시 $T_l \ge lcp_i$인 경우와 $T_l < lcp_i$인 경우로 나뉘게 된다. 
  • $T_l \ge lcp_i$인 경우를 생각해보면, 이제 $S_l = T_l$인 것으로 생각해도 무방하다는 것을 알 수 있다.
    • 그러므로, $S_l \leftarrow T_l$로 $S$를 바꾸고, $S$와 $T$를 하나로 합친다.
    • 여기서 합친다는 것은, $(T_{st}, S_{en}, S_l = T_l)$을 만든다는 것이다. 
    • 만약 여전히 $T_l > lcp_i$이면 다시 맨 처음부터 반복하면 된다.
    • 앞서 확인했듯이 $(st, en, l)$에 대응되는 suffix array 값들의 집합을 set으로 관리해야 한다. 
      • 이는 $S$에 대응되는 집합과 $T$에 대응되는 집합을 합치는 것과 같다. 그러니 small-to-large 하면 ok.
  • $T_l < lcp_i$인 경우, 이제 $S_l < lcp_i$인 경우와 같은 방식으로 대응하면 된다. 
• $S_l = lcp_i$인 경우, 단순히 $S \leftarrow (S_{st}, i = S_{en} + 1, S_l)$으로 바꾸고 set을 관리하면 된다.
• $S_l < lcp_i$인 경우, stack에 $(i-1, i, lcp_i)$를 push 하면 된다. 

모든 과정이 끝나면, stack에 원소들이 남을 것이며 $l$이 증가하는 순서일 것이다.

위 과정과 마찬가지로 pop하고 prefix들 handle 하고 스택의 다음 원소와 합치는 과정을 반복하면 답을 모두 구할 수 있다.

 

disjoint occurrence 계산을 naive 하게 할 수 있을 거라고 koosaga가 말해줬는데 안 믿은 게 문제다 ㅠㅠ 

엄청나게 어려운 자료구조를 관리해야 할 거라고 생각해서 망했다. 시간복잡도 증명이 매우 궁금한 문제.

 

꾸베릴과 알대인

 

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long int ll;
 
bool debug = false;
int ord[51111], nord[51111], cnt[51111], aux[51111];
int sfx[51111], rev[51111], lcp[51111];
string s;
int ans[51111]; 
int app[51111];
 
struct L {
    int len_com;
    int st; int en; int idx;
    L(int len_com, int st, int en, int idx): len_com(len_com), st(st), en(en), idx(idx) {}
};
 
int iidx = 0;
set<ll> VALUES[51111];
stack<L> stk;
 
void SFSA(string str) {
    int n = str.length();
    int p = 1;
    memset(ord, 0, sizeof(ord));
    for(int i=0; i<n; i++){
        sfx[i] = i;
        ord[i] = str[i];
    }
    int pnt = 1;
    while(1) {
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[min(i+p, n)]]++;
        for(int i=1; i<=n || i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        aux[--cnt[ord[min(i+p, n)]]] = i;
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[i]]++;
        for(int i=1; i<=n || i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        sfx[--cnt[ord[aux[i]]]] = aux[i];
        if(pnt == n) break;
        pnt = 1;
        nord[sfx[0]] = 1;
        for(int i=1; i<n; i++){
            if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1] + p] != ord[sfx[i] + p]){
            pnt++;
        }
        nord[sfx[i]] = pnt;
        }
        memcpy(ord, nord, sizeof(int) * n);
        p *= 2;
    }
    for(int i=0; i<n; i++) rev[sfx[i]] = i;
    int h = 0;
    for(int i=0; i<n; i++){
        if(rev[i]){
            int prv = sfx[rev[i] - 1];
            while(str[prv + h] == str[i + h]) h++;
            lcp[rev[i]] = h;
        }
        h = max(h-1, 0);
    }
}
 
int get_count(int idx, int jump) {
    int ret = 0;
    auto it = VALUES[idx].begin();
    while(it != VALUES[idx].end()) {
        ret += 1;
        it = VALUES[idx].lower_bound((*it) + jump);
    }
    return ret;
}
 
void printL(L S) {
    cout << "len_com: " << S.len_com << endl;
    cout << "st: " << S.st << endl;
    cout << "en: " << S.en << endl;
    cout << "idx: " << S.idx << endl;
}
 
void finish_handle(int upper_cut, L S) {
    if(S.len_com == 0) return;
    if(debug) {
        cout << "finish_handle " << upper_cut << endl;
        printL(S);
    }
    int num_times = S.en - S.st + 1;
    int num_app = get_count(S.idx, upper_cut);
    if(num_app < app[num_times]) return;
    int l = upper_cut;
    int r = S.len_com;
    int best = upper_cut, mid;
    while(l <= r) {
        mid = (l + r) / 2;
        if(get_count(S.idx, mid) == num_app) {
            best = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(debug) {
        cout << "num_times: " << num_times << endl;
        cout << "num_app: " << num_app << endl;
        cout << "best: " << best << endl;
    }
    if(num_app > app[num_times]) {
        app[num_times] = num_app;
        ans[num_times] = best;
    }
    else if(num_app == app[num_times]) {
        ans[num_times] = max(ans[num_times], best);
    }
}
 
L merge(L S1, L S2) {
    int from, to;
    if(VALUES[S1.idx].size() < VALUES[S2.idx].size()) {
        from = S1.idx; to = S2.idx;
    }
    else {
        from = S2.idx; to = S1.idx;
    }
    int new_st = min(S1.st, S2.st);
    int new_en = max(S1.en, S2.en);
    int new_len = min(S1.len_com, S2.len_com);
    int new_idx = to;
    for(auto it = VALUES[from].begin() ; it != VALUES[from].end() ; it++) {
        VALUES[to].insert((*it));
    }
    return L(new_len, new_st, new_en, new_idx);
}
 
int main(void) {
    cin >> s; SFSA(s);
    ans[1] = s.length();
    for(int i = 1 ; i < s.length() ; i++) {
        if(debug) cout << "on " << i << endl;
        while(!stk.empty() && lcp[i] < stk.top().len_com) {
            L S = stk.top(); stk.pop();
            int upper_cut = 0;
            if(stk.empty() || stk.top().len_com < lcp[i]) {
                upper_cut = lcp[i] + 1;
                finish_handle(upper_cut, S);
                stk.push(L(lcp[i], S.st, S.en, S.idx));
            }
            else {
                upper_cut = stk.top().len_com + 1;
                finish_handle(upper_cut, S);
                L S2 = stk.top(); stk.pop();
                L TT = merge(S2, S);
                stk.push(TT);
 
            }
        }
            
        if(stk.empty() || lcp[i] > stk.top().len_com) {
            iidx++;
            VALUES[iidx].insert(sfx[i-1]); VALUES[iidx].insert(sfx[i]);
            L Lv = L(lcp[i], i - 1, i, iidx);
            stk.push(Lv); continue;
        }
 
        if(!stk.empty() && stk.top().len_com == lcp[i]) {
            VALUES[stk.top().idx].insert(sfx[i]);
            L stk_top = stk.top(); stk.pop();
            stk.push(L(stk_top.len_com, stk_top.st, i, stk_top.idx));
        } 
    }
 
    while(!stk.empty()) {
        L S = stk.top(); stk.pop();
        int upper_cut = 1;
        if(!stk.empty()) { upper_cut = max(upper_cut, stk.top().len_com + 1); }
        finish_handle(upper_cut, S);
        if(!stk.empty()) {
            L S2 = stk.top(); stk.pop();
            L TT = merge(S2, S);
            stk.push(TT);
        }
    }
 
    for(int i = 1 ; i <= s.length() ; i++) cout << ans[i] << " ";
    cout << endl; return 0;    
}