본문 바로가기
카테고리 없음

[알고리즘] LCS(Longest Common Substring or Subsequence)

by hbIncoding 2023. 11. 6.

1. LCS란

  • 최장 공통 부분수열(L.C.Subsequence) 혹은 최장 공통 문자열 (L.C.Substring)을 말한다.
  • 각각의 차이는 아래 그림과 같다.

  • 최장 공통 부분수열은 BCDF, BCDE가 될 수 있다. 부분 수열은 분자 사이를 건너뛰어 공통이 되면 가장 긴 문자열을 찾으면 된다.
  • 최장 공통 문자열은 BCD로 부분 문자열이 아니기 때문에 한번에 이어져 있는 문자열만 가능하다.

1. 최장 공통 문자열(Longest Common Substring)

class Solution_0045 {
	public static int solution(String a, String b) {

		int[][] cal = new int[a.length() + 1][b.length() + 1];

		int ans = 0;

		for (int i = 0; i < a.length() + 1; i++) {
			for (int j = 0; j < b.length() + 1; j++) {
				if (i == 0 || j == 0) {
					cal[i][j] = 0;
				} else if (a.charAt(i - 1) == b.charAt(j - 1)) {
					cal[i][j] = cal[i - 1][j - 1] + 1;
				} else {
					cal[i][j] = 0;
				}
				ans = Math.max(ans, cal[i][j]);
			}
		}

		System.out.println(Arrays.deepToString(cal));

		return ans;
	}

	public static void main(String[] args) {
		System.out.println(solution("ABCDEF", "GBCDFE"));
	}
}

 

[[0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0], 
[0, 0, 1, 0, 0, 0, 0], 
[0, 0, 0, 2, 0, 0, 0], 
[0, 0, 0, 0, 3, 0, 0], 
[0, 0, 0, 0, 0, 0, 1], 
[0, 0, 0, 0, 0, 1, 0]]
3

 

  • 문자열을 1번 부터 세어야 하며 0인경우는  세지 않는다.
  • ABCDEF와 BCDFE의 LCS 는 BCD이다.
  • 코드 작동 과정
    • 문자열A와 문자열B를 한글자씩 비교한다
    • 두 문자가 다르다면 [i][j]에 0을 표시한다.
    • 두 문자가 같다면 [i-1][j-1] 값에 +1을 한다.
  • 위 작동 과정이 성립하는 이유는 공통 문자열은 연속되어야 하기 때문이다.
  • 문자 앞의 글자까지가 공통 문자열이라면 계속 공통 문자열 일 것이다.

2. 최장 공통 부분수열(Longest Common Subsequence)

class Solution_0046 {
	public static int solution(String a, String b) {

		int[][] cal = new int[a.length() + 1][b.length() + 1];

		int ans = 0;

		for (int i = 0; i < a.length() + 1; i++) {
			for (int j = 0; j < b.length() + 1; j++) {
				if (i == 0 || j == 0) {
					cal[i][j] = 0;
				} else if (a.charAt(i - 1) == b.charAt(j - 1)) {
					cal[i][j] = cal[i - 1][j - 1] + 1;
				} else {
					cal[i][j] = Math.max(cal[i - 1][j], cal[i][j - 1]);
				}
				ans = Math.max(ans, cal[i][j]);
			}
		}

		System.out.println(Arrays.deepToString(cal));

		return ans;
	}

	public static void main(String[] args) {
		System.out.println(solution("ABCDEF", "GBCDFE"));
	}
}

 

[[0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0], 
[0, 0, 1, 1, 1, 1, 1], 
[0, 0, 1, 2, 2, 2, 2], 
[0, 0, 1, 2, 3, 3, 3], 
[0, 0, 1, 2, 3, 3, 4], 
[0, 0, 1, 2, 3, 4, 4]]
4

  • 문자열을 1번 부터 세어야 하며 0인경우는  세지 않는다.
  • ABCDEF와 BCDFE의 LCS 는 BCDE 혹은 BCDF이다.
  • 코드 작동 과정( i-1, j-1은 문자열의 인덱스를 맞추기 위해 -1을 해주는 것으로 헷갈리면 안된다.
    • i나 j 중 0 이 있으면 0으로 입력 
    • 현재 비교중인 A의 i번째 문자와 B의 j번째 문자가 같다면 [i-1][j-1]에서+1을 해준다.
    • 두 문자가 다르다면 [i-1][j]  와 [i][j-1] 중 가장 높은 숫자를 얻어 온다.
    • 즉 해당 위치까지 오기전 최대한 연속된 공통 부분수열의 수를 얻어오는 것이다.

3. 최장 공통 부분수열 응용 문제

문자열 A와 문자열 B가 있을 때 
문자열 A의 한글자만 바꿔서 최소공통 부분수열을 최대로 만들었을 때 LCS의 길이는 몇인가

예를들어 A = "ABABC" 이고
B = "CADB"이다

현재의 최소 공통 부분수열은 "AB"이다. A의 한글자를 바꿔서 "CBABC"나 "ADABC"형태로 바꾸면
LCS는 "CAB" 나 "ADB"로 늘어날 수 있다.

 

  • 하나 바꾸면 되기에 +1을 해주면 된다고 생각할 수 도 있지만 "ABCDEF"와 "AFK"의 경우 A의 어떤걸 어떻게 바꿔도 최대 LCS가 2가 한계이다.바꾸던 안바꾸던 LCS는 2이다.
  • 이렇게 증가시킬 수 없는 경우가 어떤게 있을까?
    • A의 길이와 B의 길이중 짧은 길이만큼 LCS가 있다면 굳이 바꾸지 않아도 이미 가능한 최대이다
      • "ABCDEF" 와 "BCD처럼
    • LCS의 앞글자와 뒷글자가 A의 처음과 끝문자이거나 B의 처음과 끝문자 인경우
      • 위 예시처럼 "ABCDEF와 "AFK"의 경우 "AF"가 LSC이며 이는 A의 첫글자와 끝 글자이다.
      •  
  • 위 두가지 경우를 어떻게 판별할 것인가?
1불가)a= "ABCDEF"이고 b는 "ABFZ"일 때 배열은
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 3, 3]

2가능)a= "ABCDEF"이고 b는 "ABZF"일 때 배열은
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 3]

3불가)a= "ABCDEF"이고 b는 "AFZ"일 때 배열은
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]

4가능)a= "ABCDEF"이고 b는 "CFF"일 때 배열은
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]

5가능)a= "ABCDFZ"이고 b는 "ABCDEF"일 때 배열은
[0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3, 3]
[0, 1, 2, 3, 4, 4, 4]
[0, 1, 2, 3, 4, 4, 5]
[0, 1, 2, 3, 4, 4, 5]

6)불가능)a= "ABCDEF"이고 b는 "ABC"일 때 배열은
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 3]
[0, 1, 2, 3]
[0, 1, 2, 3]
[0, 1, 2, 3]

7)가능)a= "ABCDEFZ"이고 b는 "CFFM"일 때 배열은
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 2]

8)불가)a= "ABCDEF"이고 b는 "CFMK"일 때 배열은
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 2, 2, 2]

9)가능)a= "ABCDEF"이고 b는 "CFMF"일 때 배열은
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 2, 2, 2]
  • 아래 모든 경우는 LCS가 A나 B의 최소 길이보다 짧은 경우를 전제로 한다.
  • cal의 마지막 원소를 [M][N]이라고 했을 때 0행의 원소들> 1행의 원소들 ... 순으로 탐색한다고 했을 때
  • [M][N]원소가 아님에도 LCS의 길이와 같은 값을 가지고 있다면 확인을 해봐야한다.
    • 단 7)경우처럼 [x][N],이나 [M][x]의 원소가 아닌 원소에서 같은 값이 나온 경우는 +1이 무조건 가능하다.
      • M이나 K를 바꿔봤자 LCS는 그대로 2 이다.
    • 8)과 9)경우를 보면 b의 마지막 문자가 a의 마지막 문자와 같을 때 +1이 가능하다.

 1 : 조건 결론

  1. LCS의 길이와 두 문자열 중 짧은 문자열 길이를 비교한다.
    1. 같은 경우 >  return ans
    2. 아닐경우
      1. [M][N]까지 LCS의 길이와 같은 원소가 있는지 찾는다.
        1. 못찾는다 > return ans +1 [앞서 LCS와 짧은 문자열 길이를 이미 비교했기 때문에 가능 2)경우 생각]
        2. 찾는다 
          1. [x][N] 나 [M][x] 형태의 원소가 아닌 경우 > return ans +1  [ 7)경우라고 생각하면 된다]
          2. [x][N] 나 [M][x] 형태인 경우
            1. [x][N]인 경우엔 a의 x-1 번째 문자열 지난후 x-1와 같은 문자열이 나오는지 확인.
              1. 나온다면 return ans + 1 [7)경우]
              2. 안나온다면 return ans [8)경우혹은 3)경우]
            2. [M][y]인 경우엔 b의 y-1 번째 문자열 지난후 y-1와 같은 문자열이 나오는지 확인 .
              1. 나온다면 return ans + 1 [7)경우]
              2. 안나온다면 return ans [8)경우혹은 3)경우]

 

2. 최종 코드

class Solution_0047 {
	public static int solution(String a, String b) {

		int[][] cal = new int[a.length() + 1][b.length() + 1];

		int ans = 0;

		for (int i = 0; i < a.length() + 1; i++) {
			for (int j = 0; j < b.length() + 1; j++) {
				if (i == 0 || j == 0) {
					cal[i][j] = 0;
				} else if (a.charAt(i - 1) == b.charAt(j - 1)) {
					cal[i][j] = cal[i - 1][j - 1] + 1;
				} else {
					cal[i][j] = Math.max(cal[i - 1][j], cal[i][j - 1]);
				}
				ans = Math.max(ans, cal[i][j]);
			}
		}

		for (int i = 0; i < cal.length; i++) {
			System.out.println(Arrays.toString(cal[i]));
		}

		if (ans == Math.min(a.length(), b.length())) {
			return ans;
		} else {
			int x = a.length();
			int y = b.length();
			all:
			for (int i = 0; i < a.length() + 1; i++) {
				for (int j = 0; j < b.length() + 1; j++) {
					if (cal[i][j] == ans) {
						x = i;
						y = j;
						break all;
					}
				}
			}

			if (x == a.length() && y == b.length()) {
				return ans + 1;
			} else {
				if (y == b.length()) {
					for (int i = x; i < a.length(); i++) {
						if (a.charAt(i) == a.charAt(x - 1)) {
							return ans + 1;
						}
					}
					return ans;
				} else if (x == a.length()) {
					for (int i = y; i < b.length(); i++) {
						if (b.charAt(i) == b.charAt(y - 1)) {
							return ans + 1;
						}
					}
					return ans;
				} else {
					return ans + 1;
				}
			}
		}
	}

	public static void main(String[] args) {
		System.out.println(solution("ABCDEF", "ABFZ"));
	}
}

 

 

3. 참조 : lcs : 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는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.

velog.io

 

저작자표시

티스토리툴바