Introduction: $($Assembly MIPS $)$

Longest Common Sequence $($LCS$)$ is the longest subsequence that is common in two given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences. LCS is used in compressing genome resequencing data and to authenticate users within their mobile phone through in$-$air signatures

Implementation:

Define Function: find$\_$lcs

Inputs:

$,s1,$ an address of the first null$-$terminated string in Register $$a0.$

$,$ S$2,$ an address of the second null$-$terminated string in Register $a$1$

Outputs:

$,N,$ the size of the longest common sequence in Register $$v0.$

You are asked to write recursive function that find the LCS between two null$-$terminated strings. The function receives the address of two strings S$1$ and S$2$ as a parameter and return the length of the longest common sequence as an output. The label of the function should be declared as global $($i$.$e$.$ can be called from another file$).$ Refer to the $C$ code given below:

int find$\_$lcs$($string s$1,$ string s$2)$

$\{$

if $)==0||s2[0]==(0//$return when reach the end of

either strings.

return $0$ ;

if $\frac{s1[0]}{\frac{?}{?}}==s2[0]$ advance both pointers if the first chars are

matching

return $1+lcs(s1[1$:$n],s2[1$:$m])$;

else

return ;

$\}$

Test function find Ics$()$ :

Write assembly program that test the function you defined in part $(1).$ The code should prompt the user to enter two strings of maximum of $1024$ characters then it calls function find$\_$lcs$().$ The program should print the output to the user. An example is shown below:

Example $1$:

Enter the first string $($max $1024$ character$)$: AGGTAB

Enter the second string $($max $1024$ character$)$: GXTXAYB

The length of LCS is $4$