# 【題解】ZeroJudge d231: 97北縣賽-2-基因序列密碼問題

```#include <iostream>
using namespace std;

int main() {
string a, b;
while (cin >> a >> b){
int arr[a.length()+1][b.length()+1];
bool flag = false;
int x = 0, y = 0;

for (int i = 0; i <= a.length(); i++){
arr[i][0] = 0;
}

for (int j = 0; j <= b.length(); j++){
arr[0][j] = 0;
}

for (int i = 1; i <= a.length(); i++){
for (int j = 1; j <= b.length(); j++){
if (a[i-1] == b[j-1]){
arr[i][j] = arr[i-1][j-1]+1;
if (i > x && j > y){
cout << a[i-1];
x = i;
y = j;
flag = true;
}
}else{
arr[i][j] = max(arr[i-1][j], arr[i][j-1]);
}
}
}

if (!flag) cout << "E";
cout << "\n";
}
}
```

Python code (credit: Amy Chou)

```def getPath(i, j):
global s3
if i == 0 and j == 0:
return
if path[i][j] == 3:
s3 += s1[i-1]
getPath(i-1, j-1)
elif path[i][j] == 1:
getPath(i-1, j)
elif path[i][j] == 2:
getPath(i, j-1)

s1 = input()
s2 = input()
s3 = ""

lcs = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
path = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]

for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i-1] == s2[j-1]:
lcs[i][j] = lcs[i-1][j-1] + 1
path[i][j] = 3 #從左上方走到這一步
elif lcs[i-1][j] >= lcs[i][j-1]:
lcs[i][j] = lcs[i-1][j]
path[i][j] = 1 #從左上方走到這一步
else:
lcs[i][j] = lcs[i][j-1]
path[i][j] = 2 #從左方走到這一步

if lcs[len(s1)][len(s2)] == 0:
print("E")
else:
getPath(len(s1), len(s2))
print(s3[::-1])
```