Boj5582_공통 부분 문자열

Published: December 11, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

백준 5582 공통 부분 문자열

N^2인 쉬운 dp!

// #dp
// Comment : N^2인 쉬운 dp!
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int dp[4010][4010],ans;

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int len1 = s1.size(), len2 = s2.size();
	for (int i = 0; i < len2; i++) {
		for (int j = 0; j < len1; j++) {
			if (s1[j] == s2[i]) {
				if (i == 0 || j == 0) dp[i][j] = 1;
				else dp[i][j] = dp[i - 1][j - 1] + 1;
				ans = max(ans, dp[i][j]);
			}
		}
	}
	printf("%d", ans);
}