[백준] 18439 LCS 6 C++

효율적인 비트셋 기반 LCS(Largest Common Subsequence) 구현

두 문자열 사이의 최장 공통 부분 수열(Longest Common Subsequence, LCS)은 컴퓨터 과학에서 자주 등장하는 문제입니다. 일반적인 동적 계획법(DP)을 활용한 방식은 O(n*m)의 시간 복잡도를 가지며, 두 문자열의 길이가 클수록 메모리 사용량과 실행 시간이 증가합니다.

 

1. 문제 정의

주어진 두 문자열 a와 b에 대해:

• 공통으로 존재하는 문자의 순서를 유지하는 가장 긴 부분 수열의 길이를 계산해야 합니다.

예를 들어:

• a = "ACDBE", b = "ABCDE"가 주어졌을 때, 두 문자열의 LCS는 "ACDE"이며 길이는 4입니다.

2. 알고리즘의 핵심 아이디어

비트셋 기반 LCS 알고리즘은 아래의 원리로 작동합니다:

1. 비트셋(bset) 활용:
   • 각 문자열의 문자를 비트로 매핑합니다.
   • 문자열 b의 각 문자를 기준으로 비트셋을 생성해, 각 문자의 위치를 비트로 표현합니다.
2. 동적 계획법의 행렬 계산 대체:
   • 기존의 2차원 DP 테이블 대신, 비트 연산을 활용하여 효율적으로 상태를 업데이트합니다.
3. 비트 연산의 효율성 활용:
   • |, &, << 등의 비트 연산으로 LCS를 계산하며, 반복문이 CPU에 최적화된 방식으로 수행됩니다.

3. 코드 설명

3.1. bset 구조체

코드에서 bset은 비트셋을 다루기 위한 커스텀 자료구조입니다. 이는 C++ STL의 bitset과 유사하지만, 멀티워드(다중 64비트)를 지원하여 50,000비트 이상의 대규모 비트를 다룰 수 있습니다.

 

struct bset {
    using word = uint64_t;         // 64비트 단위
    static const int WORD_SIZE = 64;
    static const int TABLE_SIZE = 800; // 최대 50,000 비트 표현 가능

    word table[TABLE_SIZE];        // 비트셋 데이터

    // 기본 생성자: 모든 비트를 0으로 초기화
    bset() {
        memset(table, 0, sizeof(table));
    }

    // 특정 인덱스 비트를 1로 설정
    inline void setBit(int pos) {
        table[pos >> 6] |= (1ULL << (pos & 63));
    }
};

3.2. 비트셋 초기화

먼저, 문자열 b의 각 문자를 기반으로 비트셋을 구성합니다. b[j]가 특정 알파벳이라면, 그 위치에 해당하는 비트를 1로 설정합니다.

for (int j = 0; j < m; j++) {
    A[b[j] - 'A'].setBit(j);
}

A는 26개의 비트셋 배열로, 각 알파벳(A~Z)에 대한 비트셋을 저장합니다.

3.3. 비트셋을 이용한 LCS 계산

1. 초기화: bset B는 DP 상태를 표현하며, 현재까지의 LCS 정보를 저장합니다.
2. 갱신:
   • X = B | A[a[i] - 'A']:
     • 현재 문자를 포함하는 경우의 상태.
   • Y = (B << 1) | 1:
     • 이전 상태를 한 칸 이동하며, 첫 번째 비트를 설정.
   • B = X & ~(X - Y):
     • 비트 연산으로 LCS 갱신.

bset B;
for (int i = 0; i < n; i++) {
    bset X = B | A[a[i] - 'A'];
    bset Y = (B << 1) | 1ULL;
    B = X & ~(X - Y);
}

3.4. 결과 계산

최종적으로 B에 포함된 비트 1의 개수가 LCS의 길이를 나타냅니다. 이는 __builtin_popcountll()을 사용하여 빠르게 계산합니다.

long long ans = 0;
int limit = (m + 63) >> 6; // 필요한 word 개수
for (int i = 0; i < limit; i++) {
    ans += __builtin_popcountll(B.table[i]);
}

4. 시간 및 공간 복잡도

4.1. 시간 복잡도

• 비트 연산이 문자열의 길이에 따라 O(n * m / 64)로 수행됩니다.
• 일반적인 DP 방식의 O(n * m)보다 훨씬 빠르게 처리할 수 있습니다.

4.2. 공간 복잡도

• 문자열의 최대 길이를 기준으로 O(m / 64)의 메모리를 사용합니다.
• 기존 2차원 DP 배열(O(n * m))보다 메모리 사용량이 크게 줄어듭니다.

5. 코드 전체

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

struct bset {
    using word = uint64_t;
    static const int WORD_SIZE = 64;
    static const int TABLE_SIZE = 800;

    word table[TABLE_SIZE];

    bset() { memset(table, 0, sizeof(table)); }

    inline void setBit(int pos) {
        table[pos >> 6] |= (1ULL << (pos & 63));
    }

    inline bset operator|(const bset &other) const {
        bset ret;
        for (int i = 0; i < TABLE_SIZE; i++) {
            ret.table[i] = table[i] | other.table[i];
        }
        return ret;
    }

    inline bset operator<<(int shift) const {
        bset ret;
        for (int i = TABLE_SIZE - 1; i >= 0; i--) {
            ret.table[i] = (table[i] << shift);
            if (i > 0) ret.table[i] |= (table[i - 1] >> (64 - shift));
        }
        return ret;
    }

    inline bset operator-(const bset &other) const {
        return *this + (~other + 1ULL);
    }

    inline bset operator&(const bset &other) const {
        bset ret;
        for (int i = 0; i < TABLE_SIZE; i++) {
            ret.table[i] = table[i] & other.table[i];
        }
        return ret;
    }
};

static const int ALPH = 26;
bset A[ALPH];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;
    if (a.size() > b.size()) swap(a, b);

    int n = a.size(), m = b.size();
    for (int j = 0; j < m; j++) A[b[j] - 'A'].setBit(j);

    bset B;
    for (int i = 0; i < n; i++) {
        bset X = B | A[a[i] - 'A'];
        bset Y = (B << 1) | 1ULL;
        B = X & ~(X - Y);
    }

    long long ans = 0;
    int limit = (m + 63) >> 6;
    for (int i = 0; i < limit; i++) ans += __builtin_popcountll(B.table[i]);

    cout << ans << "\n";
    return 0;
}