POJ 1458 최대 공통 하위 시퀀스 LCS

4070 단어 poj
경전의 가장 긴 공통 서열 문제.
상태 전환 방정식은 다음과 같습니다.
if(x[i] == Y[j]) dp[i, j] = dp[i - 1, j - 1] +1

else dp[i, j] = max(dp[i - 1], j, dp[i, j - 1]);


문자열 X와 문자열 Y가 설치되어 있으며 dp[i, j]는 X의 전 i 문자와 Y의 전 j 문자의 가장 긴 공통 서열 길이를 나타낸다.
만약 X[i]=Y[j]라면 이 문자는 이전의 LCS와 반드시 새로운 LCS를 구성할 수 있다.
하면, 만약, 만약...Y[j]는 각각 dp[i-1][j]와 dp[i, j-1]를 고찰하고 그 중에서 비교적 큰 것을 LCS로 선택한다.
 
Source code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define ll long long

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))



using namespace std;



const int INF  = 0x3f3f3f3f;

const int MAXN = 500;



int dp[MAXN][MAXN];



int main(){

    int i, j, t, k, n, m;

    int len1, len2;

    string str1, str2;

    while(cin >> str1 >> str2){

        memset(dp, 0, sizeof(dp));

        len1 = str1.length();

        len2 = str2.length();

        for(i = 1; i <= len1; ++i){

            for(j = 1; j <= len2; ++j){

                if(str1[i - 1] == str2[j - 1]){

                    dp[i][j] = dp[i - 1][j - 1] + 1;

                }

                else{

                    dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1]);

                }

            }

        }

        cout << dp[len1][len2] << endl;

    }

    return 0;

}

좋은 웹페이지 즐겨찾기