[C++] 11479번 서로 다른 부분 문자열의 개수 2 - 문자열, 접미사 배열과 lcp 배열

11479번 서로 다른 부분 문자열의 개수 2

 

1. 문제

• 문자열 S의 서로 다른 부분 문자열의 개수를 구하시오.

<입력>

• -1-   문자열 \(S(1 \leq L \ leq 1,000,000)\)

<출력>

• -1-   서로 다른 부분 문자열의 개수

2. 재정의

• X

3. 해결 방법

• ababc의 경우 접미사 배열 ababc, babc, abc, bc, c를 (a, ab, aba, abab, ababc), (b, ba, bab, babc), ...가 부분 문자열이 됨을 알 수 있다. 이 때 겹치는 경우는 접미사 배열에서 lcp에 해당하는 경우이다. 따라서 접미사 배열 전체 글자수 \(N(N+1)/2\)에 LCP만큼 빼주면 서로 다른 부분 문자열의 개수를 구할 수 있다.
• 접미사 배열은 Manber-Myers Algorithm으로 LCP array를 구한다.

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 1000002;

// <문제>
// 문자열 S
char S[MAX_N];
// <Manber-Myers Algorithm, LCP Array>
int t, n;
int g[MAX_N], tg[MAX_N], SA[MAX_N], RANK[MAX_N], LCP[MAX_N];

// <입력>
void input() {
    cin >> S;
    n = (int)strlen(S);
}

bool cmp(int x, int y) {
    if(g[x] == g[y])
        return g[x+t] < g[y+t];
    
    return g[x] < g[y];
}

// Manber-Myers algorithm
void getSA() {
    t = 1;
    g[n] = -1;
    
    for(int i=0; i<n; i++) {
        SA[i] = i;
        g[i] = S[i] - 'a';
    }
    
    while(t <= n) {
        sort(SA, SA+n, cmp);
        tg[SA[0]] = 0;
        
        for(int i=1; i<n; i++) {
            if(cmp(SA[i-1], SA[i]))
                tg[SA[i]] = tg[SA[i-1]] + 1;
            else
                tg[SA[i]] = tg[SA[i-1]];
        }
        
        for(int i=0; i<n; i++)
            g[i] = tg[i];
        
        t <<= 1;
    }
}

// LCP array
void getLCP() {
    for(int i=0; i<n; i++)
        RANK[SA[i]] = i;
        
    int len = 0;
    
    for(int i=0; i<n; i++) {
        int k = RANK[i];
        if(k) {
            int j = SA[k-1];
            
            while(S[j + len] == S[i + len])
                len++;
            
            LCP[k] = len;
            
            if(len)
                len--;
        }
    }
}


void solve() {
    long long cnt = 0;
    
    getSA();
    getLCP();
    
    for(int i=0; i<n; i++)
        cnt += n - SA[i] - LCP[i];
    
    cout << cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

<문제 바로가기>

https://www.acmicpc.net/problem/11479

11479번: 서로 다른 부분 문자열의 개수 2

 

<Suffix array와 lcp array>

https://leyamon.tistory.com/entry/C-9248%EB%B2%88-Suffix-Array-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%A0%91%EB%AF%B8%EC%82%AC-%EB%B0%B0%EC%97%B4%EA%B3%BC-lcp-%EB%B0%B0%EC%97%B4

[C++] 9248번 Suffix Array - 문자열, 접미사 배열과 lcp 배열

 

 

※ 궁금한 것 질문 남겨주시면 답변드리겠습니다. 좋아요 눌러주시고 편하게 질문해 주세요.