BOJ)1701 Cubeditor

문제: icpc.me/1701

문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다.

N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 5001
using namespace std;
char a[MAX_N][MAX_N];
int l, r;
vector<int> pi;
void getpi(const char *c,int len) {
    pi.clear();
    pi.resize(len);
    int j = 0;
    for (int i = 1; i < len; i++) {
        while (j > 0 && c[i] != c[j])
            j = pi[j - 1];
        if (c[i] == c[j])
            pi[i] = ++j;
    }
}
int main() {
    scanf("%s", &a[0]);
    for (int i = 0; i < MAX_N; i++) {
        if (a[0][i] == '\0') {
            l = i;
            break;
        }
    }
    for (int i = 1; i < l; i++) {
        for (int j = 0; j < l - i; j++) {
            a[i][j] = a[i - 1][j + 1];
        }
    }
    for (int i = 0; i < l; i++) {
        getpi(a[i], l - i);
        for (int j : pi)
            r = max(r, j);
    }
    printf("%d\n", r);
    return 0;
}