[G5] 백준 5582 - 공통 부분 문자열 (python3)

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

5582번: 공통 부분 문자열

---

해결방법

LCS(Longest Common Subsequence, 최장 공통 부분 수열)에서 아이디어를 빌려왔다.

풀이👀

   A  B  R  A  C  A  D  A  B  R  A
E [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
C [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
A [1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1]
D [0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0]
A [1, 0, 0, 1, 0, 1, 0, 4, 0, 0, 1]
D [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0]
A [1, 0, 0, 1, 0, 1, 0, 3, 0, 0, 1]
B [0, 2, 0, 0, 0, 0, 0, 0, 4, 0, 0]
R [0, 0, 3, 0, 0, 0, 0, 0, 0, 5, 0]
B [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]
C [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
R [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]
D [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
A [1, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1]
R [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]
A [1, 0, 0, 2, 0, 1, 0, 1, 0, 0, 2]

이 문제를 읽으면서 제일 먼저 들었던 아이디어이다. 두 문자열을 위처럼 배열하고, 같은 알파벳이 만나는 지점은 대각선 위의 숫자에 +1을 한 값으로 업데이트한다. 그리고 업데이트와 동시에 가장 큰 수를 비교하면서 저장하고 있다가 출력한다.

---

코드🐱‍👓

A = input()
B = input()

arr = [ [0 for i in range(len(A))] for j in range(len(B)) ]

M = 0
for i in range(len(B)):
    al = B[i]
    for j in range(len(A)):
        if al == A[j]:
            if i > 0 and j > 0:
                arr[i][j] = arr[i-1][j-1] + 1
            else:
                arr[i][j] += 1
        M = max(arr[i][j], M)
print(M)

 

---

(사지방 캡쳐 이슈..)