Design a dynamic programming algorithm and do a proof of correctness using induction/contradiction. You do not have to program, just give pseudo code description of algorithm and the proof must be a formal proof.

Question

Suppose you are given two strings of length n each that are defined on a common alphabet A = {a0, a1, . . . , a(j1)}. Define a function f(a(k)) = k for any k {0, 1, . . . , j 1}. Give an algorithm that runs in O(j * n^2) time and finds the longest common subsequence x = x1x2 . . . between the two strings under the constraint that (from j) of f(x(k)) if not divisible by j.