In my program, I use
String to store sequences \(X\), \(Y\) and \(Z\). These three strings will be read from the input file and saved in the strings and pass in functions. I use multi-dimensional arrays to save tables.
My solution uses bottom-up dynamic programming. Using bottom-up DP can let my algorithm avoid recursion and save the memory cost that recursion incurs when it builds up the call stack.
I use four integers in table \(b\) to show the directions. They are \(1\), \(2\), \(3\) and \(8\).
In this program, I use two tables to store the situations in the processing. Table \(c\) is for saving the length of an LCS of corresponding subsequence, table \(b\) is for saving the subproblem in the \(c\) table which gives the maximum value. The table \(c\) can let me know the length of LCS. According to the value in table \(b\), I can use direction in table \(b\) to retrieve a LCS. The process is shown in my
The time complexity of my algorithm is \(O(mno)\) if \(m\), \(n\) and \(o\) stands for the length of sequences of \(X\), \(Y\) and \(Z\).
The space complexity of my algorithm is \(O(mno)\) if \(m\), \(n\) and \(o\) stands for the length of sequences of \(X\), \(Y\) and \(Z\).
Largest \(n\) that my program can manages to compute a solution is 592. The calculation time is around 5.88s. (on Macbook) In my opinion, the running out of memory is the main issue. All calculation within memory limit can be finished in reasonable time, i.e. less than or around 6s.
X: 00000000 Y: 00000010 Z: 00000001
The LCS \(W\) of \(Y\) and \(Z\) can be either
000 0000 or
My program based on dynamic programming gives the result of \(W\):
000 0001. The the LCS of \(X\) and \(W\) is
00 0000 with length
While, the optimal solution for LCS of these three strings should be
000 0000 with length
7. This optimal solution can be retrieved using the program in
Check this result by running this program:
Optimal solution can be got from the LCS algorithm for three strings in
The table shows the result of the experiments:
We can conclude from the table that \(A(n)/n\) seems converge to a constant around \(0.74\). While due to the largest number in my experiment is only 580, the converge number may larger than \(0.74\) when the \(n\) is even larger.