The space complexity required is also O(n2) if we are not careful. However, we can release the space whenever they are no longer useful. Thus, only two columns, are required for the computation. For each of the two columns, we use two arrays: one array stores the value of w(i, j) and the other array stores the starting position of the subsequence t that maximizes w(i, j). Therefore, the space complexity is O(n) for computing all w(i, j)'s. After w(i, j)'s are computed, we know the substring t that leads to the optimal w value. Therefore, we can reconstruct the alignment for t in  time and space, where n1 is the length of t, the repeated region. If n1 is still big, we can use the standard technique in [12] to reduce the space to O(n1) by doubling the computation time for reconstructing the alignment of t.