백준 5582번 - 공통 부분 문자열

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

문제에서 중요한 점은 가장 긴 공통 부문 문자열이다.

즉, 연속된 문자열이어야 한다.

이점에 착안하여 문자열 s1과 s2가 있다고 했을 때,

특정 위치에서 두개의 문자가 같다면, 바로 직전 공통 부문 문자열 길이의 값에 1을 더해줬다.

아래의 그림을 보면

문자열 ABRAC와 BABRDC 각각의 위치에서 공통 부분 문자열의 길이를 숫자로 표현했다.

동일한 문자를 발견했을 때, 바로 전의 위치의 공통 부문 문자열의 길이에 1을 더해준 것이다.

이제까지 구한 값중에서 가장 큰 값이

가장 긴 공통 부문 문자열의 길이가 된다.

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
 
int main(){
    
    string s1;
    string s2;
    
    cin>>s1>>s2;
    
    int ans=0;
    
    vector<vector<int>> vec(s1.length()+1,vector<int>(s2.length()+1,0));
    
    for(int i=1; i<=s1.length();i++){
        for(int j=1;j<=s2.length();j++){
            if(s1[i-1]==s2[j-1]){
                vec[i][j]=vec[i-1][j-1]+1;
                ans=max(ans,vec[i][j]);
            }
        }
    }
    
    cout<<ans<<endl;
    return 0;
}