LCS (longest common subsequence)

하나 이상이 존재할 수 있다

Brute-forth algorithm

모든 subsequence of X[1..n]에 대하여 이것이 Y[1..n]를 포함하고 있는지를 찾는다.

Analysis

Number of subsequences of X = 2^m
- truth table을 보고 확인할 수 있다.
Y의 time이 O(n)인 것을 확인한다.
최악의 running time은 O(n2^m)이다.
brute-forth algorithm은 좋은 게 없다.

LCS problem

X = <x1, x2, ... , xn>
Y = <y1, y2, ..., yn>
- X와 Y 둘 다에서 longest common subsequence를 찾는다.
i-th prefix
- X = <A, B, C, B, D, A, B>
- X4 = <A, B, C, B> X0; empty sequence
Step1: Theorem 15.1

Step2: A recursively solution
- cij는 sequences Xi와 Yj의 LCS이다.
Case1
- X = <A, B, C, B, D, A, B>
- Y = <B, D, C, A, B, A>
- 0일 때는 아무것도 없으므로 0으로 채운다.
- 같은 letter를 만나면 +1을 해준다.
Step4.
- (3,4)의 경우 max(2,1)=2이므로 2를 넣어준다.
Step5.
- (4, 5) → 2, 2로 같은 경우 보통 위로 화살표 표시를 해준다.
- tie-breaking 이슈
Recursive algorithm for LCS problem
```
LCS(X, Y, i, j)
if X[i] = Y[j]
		then c[i,j] <- LCS(X, Y, i-1, j-1) + 1
else c[i,j] <- max{LCS(X, Y, i-1, j), LCS(X, Y, i, j-1)}
return c[i,j]
```
- 같은 문제를 여러번 반복해야 하는 일이 생긴다.
- table에 저장함으로써, 같은 문제를 반복하지 않도록 한다.
Step3: Computing length of LCS
```
LCS-Length(X,Y)
m<-length[X]; n<-length[Y]
for i<-1 to m   c[i,0]<-0
for j<-0 to n   c[0,j]<-0
for j<-1 to n
	for i<-1 to m
		if X[i]=Y[j]
			then c[i,j]<-c[i-1,j-1]+1; b[i,j] <- 왼쪽 위 화살표
		else if c[i,j-1]>= c[i-1,j]
				then c[i,j]<-c[i,j-1]; b[i,j] <- 위 화살표
			else c[i,j]<-c[i-1,j]; b[i,j] <- 왼쪽 화살표
return c and b
```
- c는 같은 문자의 개수, b는 화살표 방향
- i가 colums, j가 row를 의미한다.
- bottom-up approach
Step4: Constructing an LCS
```
Print-LCS(b, X, i, j)
	if i=0 or j=0
		then return
	if b[i,j] = "왼쪽 위 화살표"
		then PRINT-LCS(b,X,i-1,j-1)
			print xi
	elseif b[i,j] = "위 화살표"
		then PRINT-LCS(b,X,j-1,j)
	else PRINT-LCS(b,X,i,i-1)
```
- 최종 테이블은 다음과 같다.
- 하지만 BCAB에 대해서는 결과가 나오지 않았다.
  - 만약에 (3,5)에서 왼쪽으로 갔다면 결과가 달라졌을 것이다.
  - tie-breaking
- Space: theta(mn)
- Time: theta(mn)
  - 테이블이 m*n으로 이루어져 있기 때문에 다음과 같다.
  - recursion보다 빠르다는 것을 알 수 있다.

LCS (longest common subsequence)

Brute-forth algorithm

LCS problem

Step1: Theorem 15.1

Step2: A recursively solution

Step4.

Step5.

Recursive algorithm for LCS problem

Step3: Computing length of LCS

Step4: Constructing an LCS