[알고리즘] Python 백준 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 이하이다.
출력
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.
풀이
문자열 1 : ABRACAD
문자열 2 : ECADADAB
1. 두 문자열로 2차원 배열을 생성하고 하나의 문자가 다른 문자열에 있을 때 해당 인덱스의 칸을 True 로 바꿈
2. row 와 col 이 모두 +1 되는 오른쪽 아래 대각선 방향으로 이어져있는 최대 개수가 정답
위 의 경우 4 행 1 열의 (C,C) 부터 6 행 3 열의 (D,D) 까지 3개가 정답
코드
import sys
input= sys.stdin.readline
temp1 = input().strip()
temp2 = input().strip()
if(len(temp1) > len(temp2)):
long_line = temp1
len_long = len(long_line)
short_line = temp2
len_short = len(short_line)
else:
long_line = temp2
len_long = len(long_line)
short_line = temp1
len_short = len(short_line)
del temp1, temp2
table = [[False for _ in range(len_long)] for _ in range(len_short)]
for s_idx, s in enumerate(short_line):
for l_idx, l in enumerate(long_line):
if s==l:
table[s_idx][l_idx] = True
num = len_long + len_short
start_list=[]
for i in range(len_short):
start_list.append([i, 0])
for j in range(1,len_long):
start_list.append([0,j])
result = 0
for i in start_list:
cnt = 0
row = i[0]
col = i[1]
while row < len_short and col < len_long:
if(table[row][col] == True):
cnt += 1
else:
cnt = 0
row += 1
col += 1
result = max(cnt, result)
print (result)
Author And Source
이 문제에 관하여([알고리즘] Python 백준 5582 공통 부분 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@djh0211/알고리즘-Python-백준-5582-공통-부분-문자열-dfk2zrsd저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)