파이썬에서 두 개 이상의 문자열에서 가장 긴 공통 부분 문자열 찾는 방법

가장 긴 공통 부분 문자열(Longest Common Substring) 알고리즘을 동적 프로그래밍(Dynamic Programming) 기법으로 구현하면 O(nm)의 시간 복잡도로 실행됩니다. 여기서 n과 m은 각각 비교 대상인 두 문자열의 길이입니다. 다음은 이 알고리즘을 파이썬으로 구현한 예시입니다.

예제 코드

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

print(longest_common_substring('wellbeing', 'welcome'))

실행 결과

wel

동작 원리

이 코드가 작동하는 방식은 다음과 같습니다.

• 초기화: 먼저 카운터 배열(m)의 모든 값을 0으로 초기화합니다.
• 문자 비교: 첫 번째 행부터 시작하여 문자열 s1의 각 문자를 문자열 s2의 모든 문자와 차례대로 비교합니다.
• 카운터 증가: s2의 문자를 순회하는 도중 s1의 문자와 일치하면 카운터를 1씩 증가시키고, 그 값을 대각선 한 칸 아래 위치인 m[i][j]에 저장합니다.

모든 반복이 끝나면 루프에서 계산된 인덱스를 활용해 가장 긴 부분 문자열을 잘라내어 반환합니다. 참고로 위 코드는 파이썬 3 기준으로 작성되었으며, 파이썬 2의 xrange 대신 range를 사용했습니다.

세 개 이상의 문자열로 확장하기

위 함수는 두 개의 문자열을 비교하지만, functools.reduce를 활용하면 세 개 이상의 문자열에도 손쉽게 적용할 수 있습니다. 앞서 구한 공통 부분 문자열을 다음 문자열과 계속 비교해 나가는 방식입니다.

from functools import reduce

def longest_common_substring_all(strings):
    return reduce(longest_common_substring, strings)

print(longest_common_substring_all(['wellbeing', 'welcome', 'welfare']))

실행 결과는 'wel'입니다. 즉, 'wellbeing', 'welcome', 'welfare' 세 문자열 모두에 공통으로 포함된 가장 긴 부분 문자열은 'wel'입니다.