[C++] 백준 5582번 : 공통 부분 문자열

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

5582번: 공통 부분 문자열

 

문자열 + dp 기본 문제

너무 좋은 LCS 알고리즘 설명글도 아래에 공유

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <sstream>

using namespace std;

string str1, str2;
int idx1, idx2, ans = 0;
int dp[4001][4001] = { 0, };

int main() {
	
	ios::sync_with_stdio(0);
	cout.tie(0);

	cin >> str1 >> str2;
	
	int len1 = str1.length(), len2 = str2.length();

	for (int i = 0; i < len1; i++) {
		for (int j = 0; j < len2; j++) {
			if (str1.at(i) == str2.at(j)) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
				if (ans < dp[i + 1][j + 1])
					ans = dp[i + 1][j + 1];
			}
		}
	}
	
	cout << ans;

	return 0;
}

 

 

 

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence