[알고리즘 시리즈 의 19] 최 장 공공 서브 시퀀스

제목.
최 장 공통 서브 시퀀스
분석 하 다.
두 개의 문자열 S1 과 S2 가 있 습 니 다. 가장 긴 공공 문자열, 즉 문자열 S3 를 구 합 니 다. 이것 은 S1 과 S2 의 하위 문자열 이 고 길이 가 가장 길 어야 하 며 이 길 이 를 확인 해 야 합 니 다.이 문 제 를 우 리 는 가장 긴 공공 서열 문제 라 고 부른다.가장 긴 서브 시퀀스 를 구 하 는 것 과 마찬가지 로 우 리 는 먼저 원래 의 문 제 를 하위 문제 로 나 누 었 습 니 다. 우 리 는 dp [i] [j] 로 S1 의 앞 i 문자 와 S2 의 앞 j 문자 로 구 성 된 두 개의 접두사 문자열 의 가장 긴 공공 서브 문자열 길 이 를 표시 합 니 다.분명 한 것 은 i, j 가 시간 에 비해 우 리 는 직접 답 을 줄 수 있다. 예 를 들 어 dp [0] [j] 는 반드시 0 과 같다.그러면 우리 가 이미 구 한 dp [i] [j] (0 < = i < x, 0 < = j < y) 의 모든 값 을 가정 하고 이 값 을 이어서 미 루 는 dp [x] [y], 구 한 S1 전 x 문자 로 구 성 된 접두사 문자열 과 S2 전 y 문자 로 구 성 된 접두사 문자열 의 가장 긴 공공 하위 서열 의 길 이 를 고려 합 니 다.S1 [x] = = S2 [y], 즉 S1 의 x 번 째 문자 가 S2 의 y 번 째 문자 와 같 고 각자 접두사 문자열 의 마지막 문자 이기 때문에 가장 긴 공공 문자열 이 S1 [x] 또는 S2 [y] 로 끝나 야 합 니 다.다른 부분 은 S1 의 앞 x - 1 글자 와 S2 의 앞 Y - 1 글자 의 가장 긴 공공 하위 문자열 과 같 습 니 다.그래서 이 하위 문자열 의 길 이 는 dp [x - 1] [y - 1] 보다 1 증가 합 니 다. 즉, dp [x] [y] = dp [x - 1] [y - 1] + 1 입 니 다.반대로 S1 [x]! =S2 [y], 이때 가장 긴 공공 하위 문자열 의 길 이 는 S1 의 앞 x - 1 문자 와 S2 의 앞 Y 문자 의 가장 긴 공공 하위 문자열 의 길이 와 S1 의 앞 x 문자 와 S2 의 앞 Y - 1 문자 의 가장 긴 공공 하위 문자열 의 길이 가 큰 사람 이다. 즉, 두 가지 상황 에서 얻 은 가장 긴 공공 하위 문자열 은 그 중의 한 문자열 로 인해 한 글자 의 길이 가 더 늘 어 나 지 않 는 다.다시 말 하면 dp [x] [y] = max {dp [x] [y - 1], dp [x - 1] [y]}.요약 하면 가장 긴 공공 하위 서열 문제 의 전달 조건: 두 개의 문자열 S1 과 S2 가 있다 고 가정 합 니 다. 그 중에서 S1 길 이 는 n 이 고 S2 길 이 는 m 이 며 dp [i] [j] 로 S1 전 i 문자 로 구 성 된 접두사 문자열 과 S2 전 j 문자 로 구 성 된 접두사 문자열 의 가장 긴 공공 하위 문자열 길 이 를 표시 합 니 다.

dp[0][j] = 0 （0 <= j <= m） 
dp[i][0] = 0 （0 <= i <= n）
dp[i][j] = dp[i-1][j-1] + 1 （S1[i] == S2[j]）
dp[i][j] = max{dp[i][j-1],dp[i-1][j]} （S1[i] != S2[j]） 

코드

/*--------------------------------------------- *   ：2015-02-12 *   ：SJF0115 *   : 19.        *   ：     *   ： -----------------------------------------------*/
#include <iostream>
#include <algorithm>
using namespace std;


class Solution {
public:
    int LCS(string a,string b){
        int sizea = a.size();
        int sizeb = b.size();
        if(sizea <= 0 || sizeb <= 0){
            return 0;
        }//if
        int dp[sizea+1][sizeb+1];
        //    
        for(int i = 0;i < sizea;++i){
            for(int j = 0;j < sizeb;++j){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                }//if
            }//for
        }//for
        //   
        for(int i = 1;i <= sizea;++i){
            for(int j = 1;j <= sizeb;++j){
                if(a[i] == b[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }//else
                else{
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }//else
            }//for
        }//for
        return dp[sizea][sizeb];
    }
};


int main() {
    Solution solution;
    string a("BDCABA");
    string b("ABCBDAB");
    cout<<solution.LCS(a,b)<<endl;
}