백준23495 Longest Lyndom Prefix

작성일 | In

문제 링크

  • http://icpc.me/23495

사용 알고리즘

  • Suffix Array

시간복잡도

  • $O(N \log N)$

풀이

문자열 $S$의 모든 suffix의 가장 긴 lyndon prefix word를 구하는 문제입니다.

사전 순으로 앞선 접미사부터 차례대로 처리할 것입니다. 사전 순으로 $i$번째인 접미사 $S[sa_i\cdots]$를 처리하는 상황을 생각해 봅시다.
$sf_i = S[sa_i\cdots]$보다 짧으면서 사전 순으로 앞서는, 즉 $j < i, sa_j > sa_i$를 만족하는 접미사 $sf_j = S[sa_j\cdots]$는 매우 중요한 단서를 갖고 있습니다. 만약 $sf_i$의 접두사 $P$가 $sf_j$의 일부를 포함한다면 $P$는 $sf_j \cap P$보다 사전 순으로 앞설 수 없습니다. $P$가 $sf_j \cap P$보다 사전 순으로 앞선다면 $s_i$가 $s_j$보다 앞서기 때문에 $j < i$에 모순입니다.
따라서 $s_i$의 longest lyndon prefix word의 길이는 $sa_j - sa_i$보다 클 수 없습니다.

답의 상한을 구했으니 이번에는 하한을 구할 차례입니다. $j < i, sa_j > sa_i$를 만족하면서 $sa_j$가 가장 작은(길이가 가장 긴) 접미사 $s_{j’}$를 생각해 봅시다.
정답은 $sa_{j’} - sa_i$ 이상임을 보일 수 있습니다. 만약 정답 $l$이 $0 < l < sa_{j’} - sa_i$이면 $s_i$보다 $S[sa_i+l\cdots]$이 사전 순으로 앞서야 하는데, 이는 $sa_{j’}$가 최소라는 조건과 모순이기 때문입니다.

그러므로 $s_i$의 longest lyndon prefix word의 길이는 $sa_{j’} - sa_i$입니다. std::set 등을 이용해 $O(N \log N)$ 시간에 모든 접미사에 대한 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Solve(){
    int n; string s; cin >> n >> s;
    auto [sa,lcp] = SuffixArray(s);
    vector<int> len(n), pos(n), res(n);
    for(int i=0; i<n; i++) len[i] = n - sa[i];
    for(int i=0; i<n; i++) pos[sa[i]] = i;
    set<int> st;
    res[sa[0]] = len[0];
    for(int i=1; i<n; i++){
        st.insert(len[i-1]);
        auto it = st.lower_bound(len[i]);
        res[sa[i]] = len[i] - (it != st.begin() ? *prev(it) : 0);
    }
    for(auto i : res) cout << i << " "; cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}