# 5582. 공통 부분 문자열 [링크](https://www.acmicpc.net/problem/5582) | 난이도 | 정답률(\_%) | | :----: | :---------: | |Silver I|43.342| ## 설계 ### 메모이제이션 dp를 먼저 전부 0으로 초기화한다. string A,B를 입력 받는다고 했을 때, A[i]와 B[j]가 같은 경우 dp[i+1][j+1] = dp[i][j] + 1 dp 배열의 크기는 기존 정 사이즈보다 1 크게 설정해야 한다. ## 정리 | 내 코드 (ms) | 빠른 코드 (ms) | | :----------: | :------------: | |60| | ## 고생한 점 ## 코드 ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; string A, B; int dp[4002][4002] = { 0, }; // 문자열의 최대 길이는 4000 void solution() { cin >> A >> B; int answer = 0; for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A[i] == B[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; answer = max(answer, dp[i + 1][j + 1]); } } } cout << answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity