Show that the set M = M(A, B) = {(i, j) | ai = bj} which is needed for sparse dynamic programming LCS computation, sorted in reverse column-order, can be constructed in O(s + |A| + |B| + |M|) time on...

Show that the set M = M(A, B) = {(i, j) | ai = bj} which is needed for sparse dynamic programming LCS computation, sorted in reverse column-order, can be constructed in O(s + |A| + |B| + |M|) time on a constant alphabet and in O((|A| + |B|)log |A| + |M|) time on an ordered alphabet. Observe also that this construction can be run in parallel with Algorithm 6.3 to improve the space requirement of Theorem 6.12 to O(m).