[알고리즘] BOJ 5582 공통 부분 문자열

[BOJ] 5582 공통 부분 문자열 바로가기

📍 문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

---

📍 입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

---

📍 출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

---

📍 풀이

✍ 적용 알고리즘

• 동적 프로그래밍(Dynamic Programming) 알고리즘을 적용하여 문제를 해결하였다.

✍ 문제 풀이

• 주어진 두 문자열(S1, S2)의 길이(N1, N2) 만큼의 2차원 배열(dp)을 생성한다.
• 반복문을 통해 두 문자열의 문자를 한개씩 비교한다.
• 현재 비교하는 S1과 S2의 문자가 서로 같을 경우 현재 문자 이전의 문자열까지 이어진 부분 문자열 길이에 + 1 한 값을 dp 에 갱신한다.
• 모든 문자를 확인한 후 가장 긴 공통 부분 문자열의 길이를 출력한다.

📌 ABRACADABRA, ECADADABRBCRDARA 문자열을 비교 수행한 후 나온 결과

✍ 코드

from sys import stdin
S1 = stdin.readline().strip()
S2 = stdin.readline().strip()

result = 0 # 최장 공통 부분 문자열 길이
N1, N2 = len(S1), len(S2)
dp = [[0 for _ in range(N1+1)] for _ in range(N2+1)]
for y in range(1,N2+1):
    for x in range(1,N1+1):
        if S1[x-1] == S2[y-1]: # 현재 비교하는 문자가 같을 경우
            dp[y][x] = dp[y-1][x-1] + 1 # 현재 문자열의 이전의 이어진 문자열 길이 + 1
            result = max(result, dp[y][x]) # 현재까지 이어진 문자열 중 가장 긴 문자열 저장
print(result)