LCS 설명 & 파이썬 코드

LSC 설명 블로그

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

---

LCS 코드 - https://www.acmicpc.net/problem/9251

9251번: LCS

 

astr = input()
bstr = input()
n = len(astr)
m = len(bstr)

LCS = [[0 for _ in range(m+1)] for _ in range(n+1)]
result = []

for i in range(1, n+1):
    for j in range(1, m+1):
        if astr[i-1] == bstr[j-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])
            
cur  = LCS[n][m]     
r, c = n, m  
while 1:
    if cur == 0:
        break
    if cur == LCS[n-1][m]:
        cur = LCS[n-1][m]
        n -= 1
    elif cur == LCS[n][m-1]:
        cur = LCS[n][m-1]
        m -= 1
    else:
        result.append(bstr[m-1])
        cur = LCS[n-1][m-1]
        n-=1
        m-=1
        
print(len(result))    
             
# for i in range(len(result)-1, -1 , -1):
#     print(result[i], end='')