[문자열, 파이썬] 최장 공통 부분 문자열

LCS(Longest Common Substring)

최장 공통 부분 문자열로, 공통 문자열 중 가장 길이가 긴 것을 찾아내는 알고리즘이다.
DP나 Graph 문제 풀 때 비슷한 문제를 꽤나 풀었던 거 같은데, 다시 푸니 아예 생각이 안났다. for문을 두 번 쓰는 건 알겠는데, 이차원 그래프를 돌며 각 인덱스에 해당하는 문자를 비교해서 값을 넣는 방식이 어색하다. 기본 문제이기 때문에 자꾸 연습해서 머리를 컴퓨터 방식에 적응되도록 해야겠다 @ㅅ@

a, b = map(list, input().split())
g = list([0]*(len(b)+1) for _ in range(len(a)+1))

ans = 0
for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            g[i][j] = g[i-1][j-1] +1
        else:
            g[i][j] = 0
    ans = max(max(g[i]), ans)

# print(g)
print(ans)

* 참고

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