[백준] Round words Python 3

LCS(Longest Common Subsequence, 최장 공통 부분 수열)은 두 문자열에서 공통 부분 수열 중 가장 긴 길이를 구하는 문제로, 전통적으로 DP로 해결합니다. 그러나 비트마스크를 이용하면 메모리를 절약하면서도 대규모 문자열에서 빠르게 계산할 수 있습니다. 비트마스크로 LCS를 계산하는 방식은 먼저 두 문자열 중 하나(b)의 각 문자 위치 정보를 알맞은 비트 위치에 기록하는 것을 시작으로 합니다. 예를 들어 b가 "abcac"라면 각 문자에 대해 비트마스크로 등장 위치를 표현합니다. 'a'는 10100, 'b'는 01000, 'c'는 00011처럼 각 알파벳의 위치를 비트로 표시합니다. 그다음 a의 문자들을 순회하며 현재 상태를 담는 비트마스크 B를 갱신합니다. B와 eng[ch]를 결합하고 비트를 시프트하며 새로운 상태를 계산합니다. 최종적으로 B에 켜진 비트의 수가 LCS의 길이가 됩니다. 이 과정을 통해 LCS를 빠르게 계산할 수 있습니다.

b 문자열의 모든 회전 및 역회전까지 고려하는 확장은 a와의 LCS 최댓값을 구하는 문제로 확장됩니다. 구현은 b를 두 배로 이어붙여 모든 회전을 슬라이싱으로 얻고, 역회전도 같은 방식으로 처리합니다. 예를 들어 b가 "abc"라면 bb는 "abcabc"가 되어 "abc", "bca", "cab"를 얻고, 역문자열의 경우도 같은 방식으로 추출합니다. 각 구간에 대해 lcs(a, sub)를 계산하고 최댓값을 갱신합니다. 이때 lcs 함수는 앞서 설명한 비트마스크 방법으로 최적화합니다.

solve_round_lcs 함수의 핵심은 두 단계의 순회입니다. 먼저 bb를 만들어 길이 n인 모든 회전을 구하고 각 회전에 대해 LCS를 계산합니다. 둘째로 reverse(b)의 회전을 동일하게 적용합니다. 이렇게 하면 b의 모든 회전과 역회전에서의 LCS 최댓값을 얻을 수 있습니다. 전체적으로 시간 복잡도는 문자열 길이 n에 대해 O(n^2)이며, 비트마스크를 사용해 DP 방식과 비슷한 시간 복잡도를 유지하면서 메모리 사용량과 실제 실행 속도를 높입니다. 실행 흐름은 입력으로 문자열 a와 b를 받고, solve_round_lcs(a, b) 값을 출력하는 방식으로 끝납니다.