백준 5582 : 공통 부분 문자열 c++

코드

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;



int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	string a, b;
	cin >> a >> b;
	
	int dp[a.length()][b.length()];
	
	memset(dp, 0, sizeof(dp));
	
	int x, y;
	int max = 0;
	
	for(int i = 0; i < a.length(); i++){
		for(int j = 0; j < b.length(); j++){
			if(a[i] == b[j]){
				if (i==0 || j==0)  dp[i][j] = 1;
				else dp[i][j] = dp[i-1][j-1] + 1;
			}	
			if(dp[i][j] > max) max = dp[i][j];
		}
	}
	
	cout << max;
		
	return 0;
}

알게된 점

그냥 dp문제였다.

스트링은 동적할당처럼 할 수 있었다.

dp말고 그냥 코딩으로 풀었는데, 시간초과가 나서

구글링으로 dp풀이를 봤는데, dp풀이가 훨씬 간단했다.