lcs II

 x = 'abcdef'

y = 'bcdk'

lx = len(x)

ly = len(y)

# 初始化 LCS 矩陣，大小為 (lx+1) x (ly+1)

c = [[0] * (ly + 1) for _ in range(lx + 1)]

# 填充 LCS 矩陣

for i in range(1, lx + 1):

    for j in range(1, ly + 1):

        if x[i - 1] == y[j - 1]:  # 如果字元相同

            c[i][j] = c[i - 1][j - 1] + 1

        else:

            c[i][j] = max(c[i - 1][j], c[i][j - 1])

# 追踪 LCS 實際內容

lcs = []

i,j = lx,ly

while i>0 and j>0:

    if x[i-1]==y[j-1]:

        lcs.append(x[i-1])

        i-=1

        j-=1

    elif c[i-1][j]>c[i][j-1]:

        i-=1

    else:

        j-=1

# LCS 是從右往左追踪，需要反轉

lcs = ''.join(reversed(lcs))

 

# 輸出結果

print("LCS 長度:", c[lx][ly])

print("LCS 實際內容:", lcs)

# 顯示 LCS 矩陣

print("LCS 矩陣:")

for row in c:

    print(row)