Largest-Common-SubString Algorithm

“对于程序员而言，刷了Leetcode不一定能拿offer，但是不刷肯定拿不到offer。”

Lusion鲁迅

Largest-Common-SubString Algorithm

$$
Time: \ T(n)=\Theta(mn)
\
Space: \ V(n) = \Theta(mn)
$$

LCS(X,Y):
	m = X.length - 1 
	n = Y.length - 1
	let c[0...m][0...n], s[1..m][1..n] as new array
	for i = 0 to n
		c[0][i] = 0
	for i = 1 to m
		c[i][0] = 0
	for i = 1 to m
		for j = 1 to n
			if X[i] == Y[j]
				c[i][j] = c[i-1][j-1] + 1
				s[i][j] = "hit"
			else
				if c[i][j] <= c[i-1][j]
					c[i][j] = c[i-1][j]
					s[i][j] = "up"
				else 
					c[i][j] = c[i][j-1]
					s[i][j] = "left"
	return c && s
	
PRINT-LCS()
  c,s = LCS(X,Y)
	PRINT-LCS(s,X,X.length-1,Y.length-1)

PRINT-LCS(s,X,m,n)
	if m == 0 || n == 0
		return
	if s[m][n] == "hit"
		print X[m][n]
		PRINT-LCS(s[m-1][n-1],X,m-1,n-1)
	else if s[m][n] == "up"
		PRINT-LCS(s[m-1][n],X,m-1,n)
	else PRINT-LCS(s[m][n-1],X,m,n-1)

Space optimize

2-D Vector Storage

c[i][j] comes from c[i-1][j-1], c[i-1][j], c[i][j-1]
make c[2][n] to store c[i][j]

$$
Time: \ T(n)=\Theta(m*n)
\
Space: \ V(n) = \Theta(2n)
$$

LCS(X,Y):
	m = X.length - 1 
	n = Y.length - 1
	let c[2][0...n], s[1..m][1..n] as new array
	for i = 0 to n
		c[0][i] = 0
	for i = 1 to 2
		c[i][0] = 0
	for i = 1 to m
		for j = 1 to n
			if X[i] == Y[j]
				c[i%2][j] = c[(i-1)%2][j-1] + 1
				s[i][j] = "hit"
			else
				if c[i%2][j] <= c[(i-1)%2][j]
					c[i%2][j] = c[(i-1)%2][j]
					s[i][j] = "up"
				else 
					c[i%2][j] = c[i%2][j-1]
					s[i][j] = "left"
	return c && s

1-D Vector Storage

c[i][j] comes from c[i-1][j-1], c[i-1][j], c[i][j-1]
make c[n] to store c[i][j]

c[i][j] = 0 , i==0 || j==0
c[i][j] = c[i-1][j-1], X[i] == Y[j]
c[i][j] = max{ c[i-1][j], c[i][j-1] }

$$
Time: \ T(n)=\Theta(m*n)
\
Space: \ V(n) = \Theta(n)
$$

LCS(X,Y):
	m = X.length - 1 
	n = Y.length - 1
	let c[n], s[1..m][1..n] as new array
	for i = 0 to n
		c[i] = 0
	prev = 0
	for i = 1 to m
		for j = 1 to n
			temp = c[j]
			if X[i] == Y[j]
				c[j] = prev + 1
				s[i][j] = "hit"
			else
				if c[j] <= c[j-1]
					c[j] = c[j-1]
					s[i][j] = "up"
				else
					s[i][j] = "left"
			prev = temp
	return c && s