반응형
출처: [SWEA] SW 문제해결 심화 - 문자열 알고리즘
Input
3
11
sabcabcfabc
18
trutrutiktiktappop
6
abcdef
Output
#1 3
#2 4
#3 0
한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에
가장 긴 문자열의 길이를 출력하는 문제입니다.
구현
Suffix Array를 이용하여 LCP Array를 구합니다.
① 접미사 배열 (Suffix Array)
② LCP (Longest Common Prefix)
LCP Array 중 최댓값을 구합니다.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
int L = Integer.parseInt(br.readLine());
String str = br.readLine();
// 접미사 배열(Suffix Array)
int[] suffixArray = findSuffixArray(str);
int[] lcp = findLCP(str, suffixArray);
int answer = 0;
for (int i = 0; i < L; i++) {
answer = Math.max(answer, lcp[i]);
}
System.out.println("#" + tc + " " + answer);
}
}
public static int[] findSuffixArray(String str) {
int N = str.length();
Suffix[] sa = new Suffix[N];
// 초기 인덱스, 각 접미사의 첫 글자에 맞는 사전순에 맞는 rank 지정
for (int i = 0; i < N; i++) {
// a:0, b:1, c:2, ..., z:25
int rank = str.charAt(i) - 'a';
sa[i] = new Suffix(i, rank);
}
// 접미사 앞에서 두번째 글자로 nextRank 계산
for (int i = 0; i < N-1; i++) {
// 현재 접미사의 두번째 글자과 다음 접미사의 두번째 글자와 동일.
sa[i].nextRank = sa[i+1].rank;
}
sa[N-1].nextRank = -1;
// 첫글자와 두번째 글자에 따른 정렬
// 1차적으로 rank기준으로 정렬
// (rank값이 동일시) 2차적으로 rankNext 기준으로 정렬
Arrays.sort(sa);
int[] temp = new int[N];
// logN만큼 작업 반복(4, 8, 16 ...)
for (int length = 4; length < 2 * N; length <<= 1) {
// rank값 갱신 (초기값 세팅)
int rank = 0, prev = sa[0].rank;
sa[0].rank = rank;
temp[sa[0].index] = 0;
// 두번째 원소부터 rank값 갱신
for (int i = 1; i < N; i++) {
// 앞선 접미사와 (rank, nextRank) 동일 여부 확인
if (sa[i].rank == prev && sa[i].nextRank == sa[i - 1].nextRank) {
prev = sa[i].rank;
sa[i].rank = rank;
}
else { // 다른 경우 (rank + 1) 할당
prev = sa[i].rank;
sa[i].rank = ++rank;
}
temp[sa[i].index] = i;
}
// nextRank 갱신
for (int i = 0; i < N; i++) {
int nextIdx = sa[i].index + (length / 2);
if(nextIdx >= N) {
sa[i].nextRank = -1;
continue;
}
sa[i].nextRank = sa[temp[nextIdx]].rank;
}
// 갱신된 (rank, nextRank)기준으로 접미사 배열 재정렬
Arrays.sort(sa);
}
// 접미사 배열 반환
int[] suffixArray = new int[N];
for(int i=0; i<N; i++) {
suffixArray[i] = sa[i].index;
}
return suffixArray;
}
private static int[] findLCP(String str, int[] suffixArray) {
int N = suffixArray.length;
int[] lcp = new int[N];
int[] invSuff = new int[N];
// invSuff[]에는 접미사 배열 순서 할당
// ex) suffixArr[0] = 5 > invSuff[5] = 0 (역함수 관계)
for (int i=0; i < N; i++) {
invSuff[suffixArray[i]] = i;
}
int k = 0; // LCP 길이 초기화
for (int i=0; i<N; i++) {
if (invSuff[i] == N-1){
k = 0;
continue;
}
int j = suffixArray[invSuff[i]+1];
// 일치 여부 검사
while (i+k<N && j+k<N) {
if(str.charAt(i+k) != str.charAt(j+k)) {
break;
}
k++;
}
lcp[invSuff[i]] = k;
if (k>0) {
k--;
}
}
return lcp;
}
}
class Suffix implements Comparable<Suffix> {
int index; // 초기 인덱스
int rank, nextRank;
public Suffix(int index, int rank) {
this.index = index;
this.rank = rank;
}
public int compareTo(Suffix target) {
// 같은 경우:0, 작은 경우: -1, 큰 경우: 1
if (this.rank != target.rank)
return Integer.compare(this.rank, target.rank);
// rank가 동일하면 nextRank로 비교
return Integer.compare(this.nextRank, target.nextRank);
}
}
반응형
'PS 문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] 4043 선 맞춤 (0) | 2021.03.01 |
---|---|
[SWEA] 3950 괄호 (0) | 2021.03.01 |
[SWEA] 4040 문자열의 거듭제곱 (0) | 2021.03.01 |
[SWEA] 1218 괄호 짝짓기 (0) | 2021.03.01 |
[SWEA] 3996 Poker (0) | 2021.03.01 |
댓글