https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
| E | C | A | D | A | D | A | B | R | |
| A | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| B | |||||||||
| R | |||||||||
| A | |||||||||
| C | |||||||||
| A | |||||||||
| D | |||||||||
| A | |||||||||
| B |
| E | C | A | D | A | D | A | B | R | |
| A | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| R | |||||||||
| A | |||||||||
| C | |||||||||
| A | |||||||||
| D | |||||||||
| A | |||||||||
| B |
| E | C | A | D | A | D | A | B | R | |
| A | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| R | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| A | |||||||||
| C | |||||||||
| A | |||||||||
| D | |||||||||
| A | |||||||||
| B |
| E | C | A | D | A | D | A | B | R | |
| A | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| R | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| A | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| C | |||||||||
| A | |||||||||
| D | |||||||||
| A | |||||||||
| B |
이하생략...
1. 길이가 짧은 배열을 기준으로 긴배열을 순회한다.
2. 같은 문자가 있으면 i-1, j-1 즉 바로 이전의 문자열의 최대길이에 1을 더해준다.
s = '\0' + input()
t = '\0' + input()
if len(s) > len(t):
s, t = t, s
dy = [[0 for _ in range(max(len(s), len(t))+1)]
for _ in range(min(len(s), len(t))+1)]
ans = 0
for i in range(1, len(s)):
for j in range(1, len(t)):
if s[i] == t[j]:
dy[i][j] = dy[i-1][j-1] + 1
ans = max(dy[i][j], ans)
print(ans)
'알고리즘 > BOJ' 카테고리의 다른 글
| [Python] 백준 9084 동전 (0) | 2021.10.05 |
|---|---|
| [Python] 백준 7579: 앱 (0) | 2021.10.04 |
| [Python] 백준 14226: 이모티콘 (0) | 2021.10.04 |
| [Python] 백준 2631: 줄세우기 (0) | 2021.10.04 |
| [Python] 백준 5554: 1학년 (0) | 2021.10.03 |
댓글