백준 BOJ 3033 & 1605 - 가장 긴 문자열 & 반복 부분문자열
둘이 동일한 문제라 이것도 깔끔하게 날먹했다. 이 문제는 Suffix Array와 LCP를 구현하는 문제이다 LCP의 최댓값이 바로 문제에서 원하는 정답. www.acmicpc.net/problem/3033 3033번: 가장 긴 문자열 첫째 줄
blog.koderpark.dev
와 97%쯤 동일한 문제
저기서는 LCP의 최댓값을 요구하고 있고,
이 문제는 LCP와 Suffix Array를 동시에 출력해주면 된다.
9248번: Suffix Array
Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정
www.acmicpc.net
정말로 위 링크와 다를게 없다.
그냥 출력하는 파트만 살짝 수정해 줬을 뿐이다.
#include <bits/stdc++.h>
using namespace std;
int n,t;
int suffix[567890];
int lcp[567890];
int tmp[567890];
int g[567890], tg[567890];
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(){
cin >> s;
n = s.length();
SuffixArray(s);
LCP();
for(int i=0; i<n; i++) cout << suffix[i]+1 << " ";
cout << "\nx ";
for(int i=1; i<n; i++) cout << lcp[i] << " ";
return 0;
}
깔끔하게 AC.
반응형