# LCSのPythonコード

def calculate_lcsl(S, T):
    # 配列の要素数を取得
    s_len = len(S)
    t_len = len(T)
    
    # 整数型の二次元配列 lcsl を初期化 ((s+1)行, (t+1)列) 
    # 全ての要素を未定義の値（ここでは0）で作成
    lcsl = [[0 for _ in range(t_len + 1)] for _ in range(s_len + 1)]
    
    # n=0 または k=0 のとき LCSL(n, k) = 0 とする初期化処理 
    # (Pythonの初期化で0を入れているため、明示的なループは省略可能ですが
    # アルゴリズムの流れに従って記述します)
    for n in range(s_len + 1):
        lcsl[n][0] = 0
    for k in range(t_len + 1):
        lcsl[0][k] = 0
        
    # 動的計画法による計算 [cite: 69-82]
    for n in range(1, s_len + 1):
        for k in range(1, t_len + 1):
            # 文字が一致する場合 (1) 
            if S[n-1] == T[k-1]:
                # LCSL(n, k) = LCSL(n-1, k-1) + 1 
                lcsl[n][k] = lcsl[n-1][k-1] + 1
            # 文字が一致しない場合 (2) 
            # lcsl[n][k-1] が lcsl[n-1][k] より大きい場合
            elif lcsl[n][k-1] > lcsl[n-1][k]:
                # lcsl[n][k] = lcsl[n][k-1] 
                lcsl[n][k] = lcsl[n][k-1]
            else:
                # それ以外（lcsl[n-1][k] の方が大きいか等しい場合）
                # lcsl[n][k] = lcsl[n-1][k]
                lcsl[n][k] = lcsl[n-1][k]
                
    # 最終的な最長共通部分列の長さを返す 
    return lcsl[s_len][t_len]

# テスト実行（図2および図3の例）
X = ["A", "B", "C", "B", "D", "A", "B"] 
Y = ["B", "D", "C", "A", "B", "A"]      

result = calculate_lcsl(X, Y)
print(f"最長共通部分列の長さ: {result}") # 出力は 4 になります