C++:: boj5582 <공통 부분 문자열>

jahlee·2024년 1월 12일
0

백준_골드

목록 보기
22/24
post-thumbnail

최적화를 하면서 탐색하였다가 시간초과가 난 문제이다.
dp로 풀어야하는 문제였다...

#include <iostream>
#include <vector>
using namespace std;
// 공통 부분 문자열
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int answer = 0;
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size(), 0));
    for (int i = 0; i < s1.length(); i++) {
        for (int j = 0; j < s2.length(); j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = 1;
                if (i >= 1 && j >= 1) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                answer = max(answer, dp[i][j]);
            }
        }
    }
    cout << answer << "\n";
}

0개의 댓글