Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

根據作業Hw05 Ext.5-2 實作LCS該題

求出 給定 兩個 ASCII的 text files 的 LCS

輸入:  char * file_name1, char * file_name2

輸出:  unsigned long  length_of_LCS (return value)

其他要求:
1. 必需動態配置記憶體
2. 可以處理size達1G的檔案
3. 兩周內以 E-mail 繳交給助教

若能由command line  讀取 兩個 filename  更好

function lcs() 界面變更

unsigned long long lcs( const char *ins1, const unsigned long long n1, const char *ins2, const unsigned long long n2, ofstream *store_LCS= NULL);

將 lcs() 所有相關function 存於 lcs.cpp 中 

編譯:

在 VS C++ cmd tool 下  執行 nmake

測試:

執行 test.bat

助教總是一改再改，垃圾題也可以變難題，而我就隨便打了，去你的助教。

---

#include <stdio.h>
#include <string>
#include <tchar.h>

#include <fstream>
#include <sstream>
#include <iostream>
using namespace std;

typedef unsigned long long ULL;
typedef unsigned long UL;
ULL lcs(const char *s1, const ULL n1, const char *s2, const ULL n2, ofstream *store_LCS) {
    UL *dp[2], *argdp, length_LCS;
    UL i, j, row = 0, idx;
    dp[0] = new UL[n2+1];
    dp[1] = new UL[n2+1];
    argdp = new UL[n2+1];
    for(i = 0; i <= n2; i++)
        dp[0][i] = dp[1][i] = argdp[i] = 0;
    for(i = 1; i <= n1; i++) {
        for(j = 1; j <= n2; j++) {
            if(s1[i-1] == s2[j-1]) {
                dp[row][j] = dp[1-row][j-1]+1;
                argdp[j] = argdp[j] > dp[row][j] ? argdp[j] : dp[row][j];
            } else {
                dp[row][j] = dp[1-row][j] > dp[row][j-1] ?
                    dp[1-row][j] : dp[row][j-1];
            }
        }
        row = 1 - row;
    }
    row = 1 - row;
    length_LCS = dp[row][n2];
    char *ans;
    ans = new char[length_LCS+1];
    ans[length_LCS] = '\0';
    for(i = n2, idx = dp[row][n2]; i >= 1; i--) {
        if(argdp[i] == idx)
            ans[idx-1] = s2[i-1], idx--;
    }
    if( store_LCS == NULL) {
        cout<< "The LCS is " << endl;
        cout << ans;
        cout << endl;
    }
    else if( store_LCS->is_open()) {
        (*store_LCS) << ans;
        cout << "LCS has been saved to a file." << endl;
        cout << ans << endl;
        cout << length_LCS;
    }
    delete[] ans;
    delete[] dp[0];
    delete[] dp[1];
    delete[] argdp;
    return length_LCS;
}

const std::wstring s2ws(const std::string& s);
const std::string ws2s(const std::wstring& s);
int main(int argc, char* argv[]) {
    if(argc == 1) {
        string s1, s2;
        cout << "Input 1st string:" << endl;
        cin >> s1;
        cout << "Input 2nd string:" << endl;
        cin >> s2;
        cout << "1st string=" << s1 << endl;
        cout << "2nd string=" << s2 << endl;
        lcs(s1.c_str(), s1.length(), s2.c_str(), s2.length(), NULL);
    } else {
        cout << "1st file=" << argv[1] << endl;
        cout << "2nd file=" << argv[2] << endl;
        cout << "3rd file=" << argv[3] << endl;

        ifstream fpin1(argv[1], ios::binary), fpin2(argv[2], ios::binary);
        ofstream fpout(argv[3]);
        ostringstream os1, os2;
        if(fpin1) {
            os1 << fpin1.rdbuf();
        }
        if(fpin2) {
            os2 << fpin2.rdbuf();
        }
        string s1, s2;
        s1 = os1.str();
        s2 = os2.str();
        lcs(s1.c_str(), s1.length(), s2.c_str(), s2.length(), &fpout);
    }
    return 0;
}