[BOJ] 백준 1605 반복 부분문자열

출처: https://www.acmicpc.net/problem/1605

접미사 배열(Suffix Array)  

접미사 배열(Suffix Array)

LCP (Longest Common Prefix)

LCP (Longest Common Prefix)

 

한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에

가장 긴 문자열의 길이를 출력하는 문제입니다.

 

① 접미사 배열 (Suffix Array)
② LCP (Longest Common Prefix)
Suffix Array를 이용하여 LCP Array를 구한 다음,
LCP Array중 최댓값을 구하면 됩니다.

---

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int L = Integer.parseInt(br.readLine());
        String str = br.readLine();
         
        // 접미사 배열(Suffix Array)
        int[] suffixArray = findSuffixArray(str);
         
        // LCP
        int[] lcp = findLCP(str, suffixArray);
         
        int answer = 0;
        for (int i = 0; i < L; i++) {
            answer = Math.max(answer, lcp[i]);
        }
        System.out.println(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);
    }
}