BOJ)1605 반복 부분문자열

문제: icpc.me/1605

한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에 가장 긴 문자열의 길이를 출력하는 문제이다.

Suffix Array를 이용하여 LCP Array를 구해준 뒤 LCP Array중 최댓값이 두번 이상 나타나는 문자열 중 가장 긴 문자열이다.

한 부분 문자열이 두번 이상 출현한다면 이를 접두사를 갖는 접미사들은 접미사 배열상에서 항상 인접해 있기 때문이다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 200020
using namespace std;
char str[MAX_N];
int t, n, g[MAX_N], tg[MAX_N], SA[MAX_N], r[MAX_N], LCP[MAX_N];
bool cmp(int x, int y) {
    if (g[x] == g[y]) {
        return g[x + t] < g[y + t];
    }
    return g[x] < g[y];
}
int main() {
    scanf("%d", &n);
    scanf("%s", &str);
    t = 1;
    for (int i = 0; i < n; i++) {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }        
    while (t <= n) {    
        g[n] = -1;
        sort(SA, SA + n, cmp);    
        tg[SA[0]] = 0;
        for (int i = 1; i < n; i++) {    
            if (cmp(SA[i - 1], SA[i]))
                tg[SA[i]] = tg[SA[i - 1]] + 1;
            else
                tg[SA[i]] = tg[SA[i - 1]];
        }
        for (int i = 0; i < n; i++)
            g[i] = tg[i];    
        t <<= 1;
    }
    for (int i = 0; i < n; i++)
        r[SA[i]] = i;
    int len = 0;
    for (int i = 0; i < n; i++) {
        int k = r[i];
        if (k) {
            int j = SA[k - 1];
            while (str[j + len] == str[i + len])
                len++;
            LCP[k] = len;
            if (len)
                len--;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(LCP[i], ans);
    }
    printf("%d\n", ans);
    return 0;
}