2012-11-18 16:32:00Morris
[演算法][程式作業] LCS
根據作業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;
}