[ BOJ 백준 5582번 - 공통 부분 문자열 ] 해설 및 코드

https://www.acmicpc.net/problem/5582

 

목적

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 구하자. 부분 문자열은 연속해야 한다.

 

접근법

1. 두 문자열 a,b가 입력으로 주어진다면, s[i][j]는 a문자열의 i번째와 b문자열의 j번째의 공통 부분 문자열의 길이이다. 

2. 따라서, s[i][j]는 a[i]와 b[j]가 같다면 s[i-1][j-1] + 1이고, 아니라면 0으로 값을 채워나간다. 그리고 최대 값을 갱신한다.

3. 이 문제에서 답을 담을 배열은 4000*4000까지의 공간이 필요 없으므로 2*4000으로 선언하여 사용한다.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int s[2][4000],ans=0;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string a, b; cin >> a >> b;
    
    f(j, 0, b.length())s[0][j] = (a[0] == b[j]);
    f(i, 1, a.length()){
        s[i & 1][0] = (a[i] == b[0]);
        f(j, 1, b.length())
            if (a[i] == b[j]) {
                s[i & 1][j] = s[!(i & 1)][j - 1] + 1;
                if (ans < s[i & 1][j])ans = s[i & 1][j];
            }
            else s[i & 1][j] = 0;
    }
    cout << ans;
 
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.