What Gap open Gap close Open cost (\(o\)) start end Extend cost (\(e\)) all but end all but start Furthest reaching (\(+ 1\)) all but end all but start Diagonal shift (\(k\pm 1\)) start end \begin{align} I_{s,k} &= \max\big\{M_{s\mathbf{\color{lime}-o/2-e},k-1}\,\mathbf{\color{lime}+1}, I_{s-e,k-1}+1\big\}\\ D_{s,k} &= \max\big\{M_{s\mathbf{\color{lime}-o/2-e},k+1}, D_{s-e,k+1}\big\}\\ X_{s,k} &= \max\big\{M_{s-x,k}+1, I_{s\mathbf{\color{lime}-o/2-e},k\mathbf{\color{lime}-1}}\,\mathbf{\color{lime}+1}, D_{s\mathbf{\color{lime}-o/2-e},k\mathbf{\color{lime}+1}}, \\ &\phantom{=\max\big\{}\;\mathbf{\color{lime}M_{s-o-e, k-1}+1}, \mathbf{\color{lime}M_{s-o-e, k+1}}\big\}\\ M_{s,k} &= X_{s,k} + LCP\big(A[X_{s,k}-k \dots], B[X_{x,k}\dots]\big).