カレイドスコープ: Longest Common Subsequence (LCS)

2009年10月22日星期四

Longest Common Subsequence (LCS)

Longest Common Subsequence，中文可以稱做最長子序列，這個問題的定義如下：

給定兩個序列，求其最長相同的子序列。此問題和Longest Common Substring不同，Substring中間不可以有斷點，但是subsequence可以。

問題分析：

令序列1為S1，序列2為S2
令S1 = Sub1 + elm1, S2 = Sub2 + elm2
其中elmi就是我們要求的LCS，因此有四個可能
1. elm1是LCS的一部分而elm2不是
2. elm2是LCS的一部分而elm1不是
3. elm1, elm2都是LCS
4. elm1, elm2都不是LCS

寫程式的話，就依照Dynamic programming的方式，依次的填入表格就可以，但是如何找出我們要的LCS呢？這須要back tracing才有辦法。留著下回分解吧(如果我有空的話..>"<)。

程式碼如下:

#include <iostream>
#include <iostream>
#include <iostream>
#include <iostream>
using namespace std;
void lcs(string& s, string& t);
void lcs(string& s, string& t) {
    unsigned int** c = new unsigned int*[s.length()];
    for(unsigned int i = 0; i < s.length(); ++i) {
        c[i] = new unsigned int[t.length()];
    }
    for(unsigned int i = 0; i < s.length(); ++i) {
        for(unsigned int j = 0; j < t.length(); ++j) {
            c[i][j] = 0;
        }
    }
    for(unsigned int i = 1; i < s.length(); ++i) {
        for(unsigned int j = 1; j < t.length(); ++j) {
            if(s[i] == t[j]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i][j-1], c[i-1][j]) ;
            }
        }
    }
    for(unsigned int i = 0; i < s.length(); ++i) {
        for(unsigned int j = 0; j < t.length(); ++j) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
}

int main(int argc, char* argv[])
{
    
    char szs[1024] = {0}, szt[1024] = {0};
    string s, t;
    cout << "please a string without white space.." << endl;
    cin.getline(szs, 1024);
    s = szs;
    s.insert(s.begin(), '0');
    cin.getline(szt, 1024);
    t = szt;
    cout << "please a string without white space.." << endl;
    t.insert(t.begin(), '0');
    cout << "counting..." << endl;
    lcs(s, t);
	return 0;
}

沒有留言:

張貼留言

2009年10月22日 星期四

Longest Common Subsequence (LCS)

沒有留言:

2009年10月22日星期四