문제 링크 : https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR
www.acmicpc.net
풀이
가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다.
LCS 문자열 찾기 : https://suhwanc.tistory.com/80
LCS 알고리즘
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데..
suhwanc.tistory.com
소스 코드
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
31
32
33
|
#include <iostream>
#include <algorithm>
using namespace std;
int d[4001][4001];
int main()
{
string a, b;
string ak, bk;
a = " "; b = " ";
cin >> ak >> bk;
a += ak; b += bk;
int na = a.size();
int nb = b.size();
for (int i = 1; i < na; i++) {
for (int j = 1; j < nb; j++) {
if (a[i] == b[j]) {
d[i][j] = d[i - 1][j - 1] + 1;
}
else {
d[i][j] = 0;
}
}
}
int ans = 0;
for (int i = 0; i < na; i++) {
for (int j = 0; j < nb; j++) {
if (ans < d[i][j]) ans = d[i][j];
}
}
printf("%d\n", ans);
return 0;
}
|
cs |
개발환경 : Visual Studio 2019
지적, 조언 언제든지 환영입니다~~
'백준 문제풀이' 카테고리의 다른 글
백준 5052번 전화번호 목록 (0) | 2020.05.06 |
---|---|
백준 9252번 LCS 2 (0) | 2020.02.12 |
백준 9251번 LCS (0) | 2020.02.12 |
백준 10422번 괄호 (2) | 2020.02.12 |
백준 5557번 1학년 (0) | 2020.02.12 |