Based on Theorem 2, a dynamic programming algorithm is designed. Let n be the length of the input sequence s. We compute w(i, j) in the order shown below: