문제 URL : https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
문제접근법 :
LCS(Longest Common Subsequence) 알고리즘의 축소판입니다.
2차원배열 LCS 점화식은
if (s1[i] == s2[j]) //공통부분문자열
dp[i + 1][j + 1] = dp[i][j] + 1;
else //증가문자열
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);그렇지만 문제는 공통부분 문자열을 구하는문제이기때문에
else 부분만 지우면 끝이기에 어렵지 않은문제입니다.
소스코드 :
|
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
30
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int dp[4001][4001];
void input() {
cin >> s1;
cin >> s2;
}
void solve() {
int res = 0;
for (int i = 0; i < s1.size(); i++) {
for (int j = 0; j < s2.size(); j++) {
if (s1[i] == s2[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
res = max(res, dp[i + 1][j + 1]);
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떠한 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16934 게임 닉네임 (0) | 2021.07.11 |
|---|---|
| 백준 17609 회문 (0) | 2021.07.05 |
| 백준 2531 회전 초밥 (0) | 2021.07.02 |
| 백준 20551 Sort 마스터 배지훈의 후계자 (0) | 2021.07.02 |
| 백준 1485 정사각형 (2) | 2021.07.02 |
