백준 3033 : 가장 긴 문자열

문제 링크

접미사 배열을 이용하는 문제이다. 접미사 배열을 만든 후 lcp를 구하고, 그 중 최댓값을 구하면 문제에서 요구하는 두 번이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이 그 자체를 구할 수 있다. 접미사 배열을 구하는데에 O(nlogn^2), lcp를 구하는데에 O(n)의 시간이 소요된다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21*1e8;
const int MAX = 1e9;

int n;
string str;

vector<int> sa;
vector<int> group;
vector<int> inv;
vector<int> lca;

struct Comp{
    int k;

    Comp(int _k) : k(_k)
    {

    }

    bool operator()(int i,int j)
    {
        if(group[i] != group[j]) return group[i] < group[j];
        else return group[i+k] < group[j+k];
    }
};

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin>>n>>str;

    vector<int> lca(n,0);
    for(int i = 0;i<n;i++)
    {
        sa.push_back(i);
        group.push_back(str[i]);
    }

    group.push_back(-1);

    for(int k = 1;;k*=2)
    {
        vector<int> temp(n+1,0);
        Comp cmp(k);
        temp[n] = -1;

        sort(sa.begin(),sa.end(),cmp);

        for(int i = 1;i<n;i++)
        {
            temp[i] = temp[i-1] + cmp(sa[i-1],sa[i]);
        }

        for(int i = 0;i<n;i++)
        {
            group[sa[i]] = temp[i];
        }

        if(group[sa[n-1]] == n-1) break;
    }

    for(int i = 0,k = 0;i<n;i++, k = max(0,k-1))
    {
        if(group[i] == n-1) continue;

        for(int j = sa[group[i]+1];j+k < n && i+k < n && str[j+k] == str[i+k];k++);
        lca[group[i]] = k;
    }

    cout<<*max_element(lca.begin(),lca.end());
    return 0;
}