[BOJ] 공통 부분 문자열

 

 

문제 

 

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

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

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

 

 

 

해설 코드 

 

import sys
input = sys.stdin.readline
a,b = input().rstrip(),input().rstrip()
answer = 0
dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]

for i in range(1,len(a)+1):
  for k in range(1,len(b)+1):
    if a[i-1] == b[k-1]:
      dp[i][k] = dp[i-1][k-1] + 1
      answer = max(dp[i][k],answer)
print(answer)

		a	b	c	d
	0	0	0	0	0
b	0	0	1	0	0
c	0	0	0	2	0
d	0	0	0	0	3

분석 > 위 코드는 아래의 표를 코드로 나타낸 것이다. 결국 최장 공통 부분 문자열은 3이라는 것을 알 수 있다. 

 

 

 

5582번: 공통 부분 문자열