글 읽기 - Suffix Array와 LCP로 풀 수 없는 문제인가요?

glanceyes 3년 전 0

13275와 같은 문제로 생각해서 LCP로 문제를 풀었는데 97퍼센트에서 틀렸습니다가 뜹니다.

혹시나 싶어서 13275 통과한 코드도 그대로 실행했는데 틀렸습니다가 뜨네요...

LCP로 풀 수 없는 문제여서 그런 건가요, 아니면 단순 코드 상의 문제인 걸까요?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int check(vector<vector<int>>& group, int i, int j, int k, int n) {
    int cnt = 0;
    while(i < n && j < n && k >= 0){
        if (group[k][i] == group[k][j]){
            cnt += (1 << k);
            i += (1 << k);
            j += (1 << k);
        }
        k -= 1;
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string str; cin >> str;
    string s = str + "#";
    reverse(str.begin(), str.end());
    s += str;
    
    int str_len = (int)str.size();
    int n = (int)s.size();
    vector<int> suffix_array(n);
    vector<vector<int>> group(22, vector<int>(n + 1));
    
    for (int i = 0; i < n; i++){
        suffix_array[i] = i;
    }
    
    for (int i = 0; i < n; i++){
        group[0][i] = s[i];
    }
    group[0][n] = -1;
    
    int last = 0;
    
    for (int k = 0, len = 1; len / 2 < n; k++, len *= 2){
        auto cmp = [&](int u, int v){
            if (group[k][u] == group[k][v]) {
                return group[k][u + len] < group[k][v + len];
            }
            else{
                return group[k][u] < group[k][v];
            }
        };
        
        sort(suffix_array.begin(), suffix_array.end(), cmp);
    
        group[k + 1][suffix_array[0]] = 0;
        
        for (int i = 1; i < n; i++){
            if (cmp(suffix_array[i - 1], suffix_array[i])){
                group[k + 1][suffix_array[i]] = group[k + 1][suffix_array[i - 1]] + 1;
            }
            else {
                group[k + 1][suffix_array[i]] = group[k + 1][suffix_array[i - 1]];
            }
        }
        
        group[k + 1][n] = -1;
        last = k + 1;
    }
    
    int ans = 0;
    for (int i = 1; i < n; i++){
        if ((suffix_array[i - 1] < str_len && suffix_array[i] > str_len) ||
            (suffix_array[i - 1] > str_len && suffix_array[i] < str_len))  {
            ans = max(ans, check(group, suffix_array[i - 1], suffix_array[i], last, n));
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Suffix Array와 LCP로 풀 수 없는 문제인가요?

glanceyes 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말