[BOJ] 5582 공통부분문자열

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

5582번: 공통 부분 문자열

그냥 LCS문제인줄 알았는데 공통되는 문자열을 구해야하기 때문에 공통된 문자들이 연속적이어야 한다는게 기존 LCS문제와 달랐다.

기존 LCS에서 LCS[i][j]가 나타내는 것이 한 문자열의 i번째와 다른 문자열의 j번째까지 공통된 문자의 개수였다면

이 문제에서 LCS[i][j]가 의미하는 바는 한 문자열의 i번째와 다른 문자열의 j번째까지의 공통 부분 문자열의 크기를 저장해야 한다.

 

따라서 문자가 서로 다를 경우 LCS[i-1][j]와 LCS[i][j-1] 중 큰 값을 가져오는 것이 아니라, 그냥 0처리를 하고 넘어가야 한다.

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define endl '\n'
#define ll long long

using namespace std;

string s1,s2;
int n,m;

int LCS[4001][4001];

void input() {
    cin>>s1>>s2;
    n=s1.size();
    m=s2.size();
}

void init() {
}


int solution() {
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s1[i-1]==s2[j-1]){
                LCS[i][j]=LCS[i-1][j-1]+1;
                ans=max(LCS[i][j],ans);
            }
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    cout<<solution();
    return 0;
}