【題解】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";
    }
}

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])