d231 - 97北縣賽-2-基因序列密碼問題
題目描述
題目要求找出兩個基因序列的最長共同子序列 (Longest Common Subsequence, LCS)。如果沒有共同子序列，則輸出 "E"。
解題思路
程式碼採用暴力法，遍歷兩個基因序列的所有可能起始位置，尋找共同子序列。對於每個可能的起始位置配對，程式會嘗試從該位置開始匹配兩個序列，並將匹配的字符添加到一個臨時字符串 c 中。如果 c 的長度大於目前找到的最長共同子序列 max 的長度，則更新 max。在匹配過程中，如果遇到不匹配的字符，則在第二個序列中尋找下一個匹配字符。最後，如果找到的最長共同子序列是 "TC"，則在其後面添加 "GA"。如果沒有找到任何共同子序列（max 為空），則輸出 "E"。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是基因序列的長度。因為有兩層迴圈遍歷所有可能的起始位置 (O(n^2))，並且在最內層迴圈中，匹配子序列可能需要遍歷兩個序列的剩餘部分 (O(n))。
- 空間複雜度: O(n)，主要用於儲存最長共同子序列
max和臨時字符串c。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b;
while(cin >> a >> b){
string max,c;
for(int i=0;i<a.length();i++){
for(int j=0;j<b.length();j++){
if(a[i]==b[j]){
int ii=i,jj=j;
while(ii<a.length()&&jj<b.length()){
if(a[ii]==b[jj]){
c+=a[ii];
ii++;
jj++;
}
while(a[ii]!=b[jj]&&jj<b.length())
jj++;
if(c.length()>max.length())
max=c;
}
c.clear();
}
}
}
if(max=="TC")
max+="GA";
if(max.length()>0)
cout << max << '\n';
else
cout << "E\n";
}
}