[동적계획법] 두 문자열 비교하기 ( Longest Common SubString )

 

예제 ) 두 문자열의 최장 공통 문자열의 길이를 찾으시오

 

 

ASEFSDCA 와 SESDASEF

 

 

Common SubString은 연속적으로 공통된 부분 문자열을 의미한다. 

 

ASEFSDCA 와 SESDASEF

 

인간은 직관으로 공통된 문자열을 찾을 수 있지만 최장 공통 문자열을 찾기란 쉽지않다 또한 컴퓨터는 직관을 갖고 있지 않다. 그러므로 포인터를 사용하여 두 문자열의 문자를 하나씩 비교해야 한다. 두 문자열을 비교하려면 두 개의 포인터가 필요하다. 두 개의 포인터를 움직이며 두 문자열의 문자를 하나씩 비교해본다. 

 

 

 

포인터가 비교하는 모든 경우를 살펴보려면 이차원 테이블이 필요하다.

 

 

이차원 테이블에서 '대각선'은 의미가 크다.

 

 

포인터A와 포인터B가 동시에 한 칸씩 이동하면 대각선으로 한 칸 이동한다. 

 

 

포인터A로 ASE까지 탐색하고 포인터 B로 SE까지 탐색했을 때, 공통된 문자열의 길이는 2이다.

 

포인터A와 포인터B가 한 칸씩 이동했을 때, 두 포인터가 가리키는 문자가 동일하면 2에 +1을 한다.  만약 동일하지 않으면 0을 넣는다. 0을 넣으므로써 연속이 끝났음을 나타낸다. 

 

고로, 규칙은 아래와 같다.

 

1) 동일한 문자가 나오면 대각선 방향으로 +1씩 한다.

2) 동일한 문자가 나오지 않으면 0을 넣어 문자열 연속이 끝남을 표시한다. 

 

그럼 포인터를 이동시켜 이차원 테이블을 채워보자.

 

포인터A를 고정하고 포인터B를 이동시켜보았다. 동일한 문자 A를 제외하고는 모두 0을 넣어준다.

 

 

포인터A는 AS까지 탐색했다.

포인터B는 SESDAS까지 탐색했다. 

 

현재 포인터A와 포인터B는 동일한 문자 S를 가리킨다. 

 

이전 대각선 방향의 데이터를 확인해보자.

 

포인터A가 A까지 탐색하고

포인터B가 SESDA까지 탐색했을때 공통 문자열은 1이었다.

 

고로, 1 + 1을 하면 2가 된다. 

 

이런 방식으로 테이블을 모두 채워보자.

 

 

테이블에서 확인 가능하듯이, 최장 공통 문자열의 길이는 4이다.

 

 

---

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성