💡 **LCS**는 주로 **최장 공통 부분 수열**을 말한다.
**최장 공통 문자열**을 말하기도 한다.
부분 수열과 부분 문자열의 차이점은 위와 같다.
최장 공통 문자열 (Longest Common Substring)
for i in range(len(string_A)) :
for j in range(len(string_B)):
if i == 0 or j == 0
LCS[i][j] == 0
elif string_A[i]== string_B[j]:
LCS[i][j] = LCS[i-1][j-1] + 1
else :
LCS[i][j] = 0
부분 수열 보다 조금 더 쉽고 최장 공통 부분 수열을 구하는데 사용됨
우선 LCS라는 2차원 배열을 이용해서 두 문자열을 행과 열에 매칭
과정
- 문자열 A와 문자열 B의 한 글자 끼리 비교해본다
- 두 문자가 다르다면 LCS[i][j]에 0을 표시
- 두 문자가 같다면 LCS[i][j] = LCS[i-1][j-1] +1
- 위 과정 반복
최댓값을 찾으면 탐색 종료
최댓값은 LCS 의 max 값!
최장 공통 부분수열 (Longest Common Subsequence) 길이 구하기
if i == 0 or j == 0 :
LCS[i][j] = 0
elif string_A[i] == string_B[j] :
LCS[i][j] = LCS[i-1][j-1] + 1
else :
LCS[i][j] = max(LCS[i -1][j],LCS[i][j-1])
과정
- 문자열 A와 문자열 B의 한 글자 끼리 비교해본다
- 두 문자가 다르다면 LCS[i-1][j]와 LCS[i][j-1] 중 큰 값을 찾아 표시
- 두 문자가 같다면 LCS[i][j] = LCS[i-1][j-1] + 1
- 위 과정 반복
부분 수열은 연속된 값이 아니기 때문에 현재의 문자를 비교하는 과정
이전의 공통된 부분 수열은 계속 유지된다.
이전의 과정이 바로 LCS[i-1][j]와 LCS[i][j-1]
최장 공통 부분수열 (Longest Common Subsequence) 찾기
- 이제 위의 과정을 통해 길이를 알았음
- 만들어둔 LCS 배열을 통해 값을 찾아볼 수 있다
- 경우에 따라 여러가지 답이 나올 수 있다
과정
- LCS 배열의 가장 마지막 값에서 시작.
결과 값을 저장할 result 배열 준비
- LCS[i-1][j]와 LCS[i][j-1] 중 현재 값과 같은 값을 찾음
- 만약 같은 값이 있다면 해당 값으로 이동
- 같은 값이 없다면 result 배열에 해당 문자를 넣고 LCS[i-1][j-1]로 이동
- 2번 과정 반복하다가 0으로 이동하게 되면 종료 …..!
배열의 역순이 LCS !