LCS2(longest common subsequence) 알고리즘

가장 긴 공통 부분 문자열 찾기 알고리즘

#include <iostream>
#include <string>

using namespace std;

int lcs[1001][1001];
int main()
{
    //int memoization[][];
    string str1;
    string str2;

    cin >> str1;
    cin >> str2;

    //앞에 0을 더해준다.
    str1 = '0' + str1;
    str2 = '0' + str2;

    int len1 = str1.size();
    int len2 = str2.size();

    for (int i = 0; i < len1; i++)
    {

        for (int j = 0; j < len2; j++)
        {
            if (i == 0 || j == 0)
            {
                lcs[i][j] = 0;
                continue;
            }
            if (str1.at(i) == str2.at(j)){
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                //str3 += str1.at(i);
            }
            else
            {
                if (lcs[i - 1][j] > lcs[i][j - 1])
                    lcs[i][j] = lcs[i - 1][j];
                else
                    lcs[i][j] = lcs[i][j - 1];
            }
        }
    }
    return 0;
}

1. 1행과 1열은 0으로 초기화한다.
2. 행렬이므로 2중 for문 사용
3. str1의 i번째 문자 == str2의 j번쨰 (왼쪽 위 대각선 + 1)을 대입
4. 같지 않은 경우 (왼쪽과 위쪽 중 큰 값)을 대입

	char result[1001];
	
	int i = len1 - 1, j = len2 - 1 , cnt = 0;
	//행렬 우하향 설정
	while (i != 0 && j != 0){
		if (lcs[i - 1][j] == lcs[i][j])//왼쪽 오른쪽 비교
			i--;
		else if (lcs[i][j - 1] == lcs[i][j])
			j--;
		else
		{
			result[cnt++] = str1[i];
			i--;
			j--;
		}
	}
	//result[cnt++] = str1.at(i);
	result[cnt] = NULL;
	int temp;
	for (int i = 0; i < (cnt / 2); i++)
	{
		temp = result[i];
		result[i] = result[cnt - 1 - i];
		result[cnt - 1 - i] = temp;
	}
	cout << result  << endl;

 

알고리즘 설명

1. 같으면 그 쪽으로 이동한다.
2. 둘 다 같지 않으면 대각선으로 이동한다.