The optimal substructure of the longest common subsequence problem gives the recursive formula

which is based on prefixes of the two inputs, i.e., X[1..i] and Y [1..j]. Rewrite the recursive formula using suffixes instead of prefixes, i.e., X[i..m] and Y [j..n].

if i = 0 or j = 0 , if i, j > 0 and x,-y, , max(ct, J