파이썬 SequenceMatcher로 두 문자열의 가장 긴 공통 부분 문자열 찾기

개요

두 개의 문자열이 주어졌을 때, 두 문자열에 공통으로 포함된 가장 긴 부분 문자열(longest common substring)을 찾아 출력하는 것이 이번 문제의 목표입니다. 파이썬에서는 표준 라이브러리인 difflib 모듈의 SequenceMatcher.find_longest_match() 메서드를 활용하면 복잡한 알고리즘을 직접 구현하지 않고도 이 문제를 간단하게 해결할 수 있습니다.

difflib.SequenceMatcher 클래스는 요소가 해시 가능(hashable)하기만 하면 문자열, 리스트 등 어떤 유형의 시퀀스 쌍이라도 비교할 수 있는 유연한 클래스입니다.

find_longest_match() 메서드

find_longest_match(a, x, b, y)는 첫 번째 시퀀스의 a[a:x] 구간과 두 번째 시퀀스의 b[b:y] 구간 사이에서 가장 긴 일치 블록(matching block)을 찾아 반환합니다. 반환되는 객체는 일치 시작 위치(a, b)와 일치 길이(size) 정보를 담고 있어, 이를 활용해 실제 부분 문자열을 추출할 수 있습니다.

예제

입력: str1 = "pythonprogramming"
      str2 = "pro"
출력: pro

알고리즘

두 개의 문자열을 입력받습니다.
입력받은 문자열로 SequenceMatcher 객체를 초기화합니다.
find_longest_match()를 호출하여 가장 긴 공통 부분 문자열의 위치와 길이를 찾습니다.
결과 부분 문자열을 출력합니다.

예제 코드

# 파이썬으로 가장 긴 공통 부분 문자열 찾기
from difflib import SequenceMatcher

def matchsubstring(m, n):
    seqMatch = SequenceMatcher(None, m, n)
    match = seqMatch.find_longest_match(0, len(m), 0, len(n))
    if match.size != 0:
        print("공통 부분 문자열 ::>", m[match.a: match.a + match.size])
    else:
        print('가장 긴 공통 부분 문자열을 찾지 못했습니다')

# 실행부
if __name__ == "__main__":
    X = input("첫 번째 문자열 입력: ")
    Y = input("두 번째 문자열 입력: ")
    matchsubstring(X, Y)

실행 결과

첫 번째 문자열 입력: pythonprogramming
두 번째 문자열 입력: pro
공통 부분 문자열 ::> pro

참고 사항

SequenceMatcher는 내부적으로 Ratcliff-Obershelp 알고리즘에 기반한 휴리스틱 방식을 사용하므로, 대부분의 실용적인 상황에서 빠르게 동작합니다. 다만 매우 긴 문자열이나 성능이 중요한 대규모 데이터 처리에는 접미사 배열(suffix array)이나 접미사 자동차(suffix automaton) 기반의 O(N+M) 알고리즘이 더 적합할 수 있습니다. 또한 공통 부분 문자열이 여러 개 존재하는 경우, SequenceMatcher는 그중 하나만 반환한다는 점도 유의해야 합니다.