[백준 5582] 공통 부분 문자열 (python)

5582번: 공통 부분 문자열

---

 

DP를 사용하자! 시간초과가 나서 Pypy3으로 제출하였다.

아래 문제와 비슷하지만 연속되어있는 공통된 문자열을 찾는 것이 다르다.

[백준 9251] LCS (python)

 

import sys
input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()

result = 0
arr = [[0]*(len(B)+1) for _ in range(len(A)+1)]
for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1] == B[j-1]:
            arr[i][j] = arr[i-1][j-1] + 1
            result = max(arr[i][j], result)

print(result)