파이썬 - 공통 부분 문자열 구하기

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

이 문제처럼 두 문자열에서 공통 부분 문자열을 구하는 문제들이 있다.

이러한 종류의 알고리즘 문제는 이차원 그래프로 DP를 적용시키면 쉽게 해결할 수 있다.

import sys

A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()


N = len(A)
M = len(B)

ans = 0

DP = [ [0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):

        if A[i-1] == B[j-1]:
            DP[i][j]+=DP[i-1][j-1]+1
            print(i,j,DP[i][j])
            ans = max(DP[i][j],ans)

print(ans)

KABDE와 ABDXY의 공통 부분 문자열을 구한다고 치면 이러한 DP그래프로 공통부분의 길이를 구할 수 있다.

공통부분 문자열 자체를 찾는다면 해당 DP 그래프에서 i,j의 값을 활용해 구할 수 있다.