백준 5582 c++ "공통 부분 문자열" -PlusUltraCode-

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

 

[필자 사고]

LCS 즉 최장 공통 부분수열과 

최장 공통 부분 문자열 차이를 알아야 풀 수 있다.

전자는 문자열이 붙어있지 않아도 된다. 그냥 존재하기만 하면된다.

그래서 문자열이 같으면 dp[i][k] = dp[i-1][k-1] +1 을하고

같지 않다면 max(dp[i-1][k], dp[i][k-1]) 형태로 업데이트하면 된다.

 

근데 최장공통 부분 문자열은 순서가 중요하므로

같으면 전자와 같은 형태로 식을 만들고\

같지 않다면 이전 기록들은 필요없으므로 dp[i][k] =0 으로 해놔야된다.

 

아래는 자세한 코드해설이다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 사용자로부터 두 문자열을 입력받고, 이를 각각 str1과 str2에 저장한다.
편의상 각 문자열의 맨 앞에 공백 문자 하나를 삽입하는데, 이는 DP 테이블을 인덱스 1부터 사용하기 위함이다. 이렇게 하면 인덱스 처리를 더 간편하게 할 수 있다.
이후, dp는 최대 길이 4000을 고려하여 4001 x 4001 크기의 2차원 벡터로 초기화된다. 각 요소는 0으로 설정되어 공통 문자열의 길이를 누적해 나갈 준비를 한다.

---

3. 공통 부분 문자열 계산 (Game_Start 함수)

Game_Start() 함수는 동적 프로그래밍을 이용하여 두 문자열 사이의 **최장 공통 부분 문자열(Longest Common Substring)**의 길이를 계산한다.
두 개의 이중 반복문을 통해 str1의 각 문자와 str2의 각 문자를 순차적으로 비교한다.
만약 현재 비교 중인 두 문자가 같다면, 해당 위치의 dp 값은 왼쪽 위 대각선(dp[i-1][k-1])의 값에 1을 더한 값이 된다. 이는 현재 위치까지 연속적으로 일치하는 문자의 개수를 나타낸다.
반면, 문자가 다르다면 연속성이 끊긴 것이므로 해당 dp 값은 0으로 초기화된다.
이 과정에서 매번 최대값을 갱신하여 최장 공통 부분 문자열의 길이를 추적하며, 최종적으로 그 값을 출력한다.

---

4. DP 테이블 출력 (Print 함수)

Print() 함수는 dp 배열 전체를 출력하는 디버깅용 함수이다.
공통 부분 문자열 계산이 끝난 뒤 호출되어 각 위치별로 계산된 문자열 길이들을 확인할 수 있도록 해준다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

string str1, str2;
vector<vector<int>> dp;

void Input() {
	cin >> str1 >> str2;
	str1.insert(0," ");
	str2.insert(0, " ");


	dp.assign(4001, vector<int>(4001,0));

}

void Print() {
	for (int i = 1; i < str1.size(); i++) {
		for (int k = 1; k < str2.size(); k++) {
			cout << dp[i][k] << " ";
		}
		cout << '\n';
	}
}

void Game_Start() {
	int resultCount = 0;
	for (int i = 1; i < str1.size(); i++) {
		for (int k = 1; k < str2.size(); k++) {
			if (str1[i] == str2[k]) {
				dp[i][k] = dp[i - 1][k - 1] + 1;
				resultCount = max(resultCount, dp[i][k]);
			}
			else {
				dp[i][k] = 0;
			}
		}
	}

	Print();
	cout << resultCount;
}




int main(void) {
	Input();
	Game_Start();
}