반응형
https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
[ 문제풀이 ]
1. 문자열 str1, str2를 입력 받습니다.
2. str1[ i ] 와 str2[ j ]가 일치할 때 arr[ i ][ j ] = arr[ i - 1 ][ j - 1 ] + 1의 점화식을 통해 최댓값을 ans에 저장합니다.
3. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<iostream> #include<string> using namespace std; int arr[4001][4001]; int ans; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str[2]; cin >> str[0] >> str[1]; str[0] = '1' + str[0]; str[1] = '1' + str[1]; for (int i = 1; i < str[0].size(); i++) { for (int j = 1; j < str[1].size(); j++) { if (str[0][i] == str[1][j]) { arr[i][j] = arr[i - 1][j - 1] + 1; ans = max(ans, arr[i][j]); } } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2228번 - 구간 나누기 (C++) (0) | 2022.10.24 |
|---|---|
| [ 백준 ] 2133번 - 타일 채우기 (C++) (0) | 2022.10.23 |
| [ 백준 ] 2225번 - 합분해 (C++) (0) | 2022.10.21 |
| [ 백준 ] 2011번 - 암호코드 (C++) (0) | 2022.10.20 |
| [ 백준 ] 2631번 - 줄세우기 (C++) (0) | 2022.10.19 |