WITHOUT USING CHATGPT: What is the main difference between the Longest Common Subsequence $($LCS$)$ and

the longest common substring of two sequences of characters?

$(2)[35]$ Use the LCS$-$LENGTH procedure to find the Longest Common Subsequence $($LCS$)$

of two sequences: A $<1,0,0,1,0,1,0,1>$ and B $<0,1,0,1,1,0,1,1,0>.$ You need to

show the step$-$by$-$step procedure based on a table and also illustrate the path to

reconstruct the LCS you have found by drawing lines through the centers of the grids on

the path in the table.

$(3)[15]$ What is the running time of the LCS algorithm based on dynamic programming?

Justify your answer.