백준 BOJ 3033 & 1605 - 가장 긴 문자열 & 반복 부분문자열

둘이 동일한 문제라

이것도 깔끔하게 날먹했다.

이 문제는 Suffix Array와 LCP를 구현하는 문제이다

LCP의 최댓값이 바로 문제에서 원하는 정답.

 

www.acmicpc.net/problem/3033

3033번: 가장 긴 문자열

www.acmicpc.net/problem/1605

1605번: 반복 부분문자열

배열이 상상히 많이 들어갔는데

어떻게 다 들어가네;;

 

#include <bits/stdc++.h>
using namespace std;

int n,t;
int suffix[234567];
int lcp[234567];
int tmp[234567];
int g[234567], tg[234567];
string s;

bool compare(int a, int b){
	if(g[a] == g[b]) return g[a+t]<g[b+t];
	return g[a]<g[b];
}

void SuffixArray(string str){
	t = 1;
	n = str.length();
	for(int i=0; i<n; i++){ suffix[i] = i; g[i] = str[i]-'a'; }
	
	while(t<=n){
		g[n] = -1;
		sort(suffix, suffix+n, compare);
		tg[suffix[0]] = 0;
		
		for(int i=1; i<n; i++){
			if(compare(suffix[i-1], suffix[i])) tg[suffix[i]] = tg[suffix[i-1]] + 1;
			else tg[suffix[i]] = tg[suffix[i-1]];
		}
		
		for(int i=0; i<n; i++) g[i] = tg[i];
		t*=2;
	}
}
 
void LCP(){
	for(int i=0; i<n; i++) tmp[suffix[i]] = i;
	int len = 0;
	for(int i=0; i<n; i++){
		if(tmp[i]){
			int j = suffix[tmp[i]-1];
			while(s[j+len] == s[i+len]) len++;
			lcp[tmp[i]] = len;
			
			if(len) len--;
		}
	}
}

int main(){
	int n;
	cin >> n;
	cin >> s;
	
	SuffixArray(s);
	LCP();
	
	int ans = -1;
	for(int i=0; i<n; i++) ans = max(ans, lcp[i]);
	printf("%d", ans);
}

깔끔하게 AC를 받아줬다.