$(5)$ Assignment: Longest Common Substring

Assignment Instructions:

Step $1$: Implement an example of Longest common substring as described above.

Your program should take in $2$ strings, you can assume for this assignment that they are identical in length.

You should create a lookup table similar to the previous slide that shows the dynamically growing table that can ultimately be used to determine an answer.

For example, if your input strings were $$ABAB$$ and $$BABA$$ your program$$s output should be a $2$D grid similar to what is shown in the previous slide along with the solution, which in this case is a tie between $$BAB$$ and $$ABA$$ since the largest value is a $3.$

Step $2$: You can show just one of the winners in your solution since there is a tie in this example case.

Step $3$: You can assume that there is at least a single shared character in both strings, so you do not need to solve for the case of no matching sequence.

Assignment Specifications:

You must use the C$++$ programming language to accomplish this.

#include

#include

#include

using namespace std;

$//$ Function to print the dynamic programming table

void printDPTable$($const vector$>$& dp$,$ const string& str$1,$ const string& str$2)\{$

cout $<<""$;

for $($char ch : str$2)\{$

cout $<<$ ch $<<""$;

$\}$

cout $<<$ endl;

for $($int i $=0$; i $<=$ str$1.$length$()$; i$++)\{$

if $($i $==0)\{$

cout $<<""$;

$\}$ else $\{$

cout $<<$ str$1[$i $-1]<<""$;

$\}$

for $($int j $=0$; j $<=$ str$2.$length$()$; j$++)\{$

cout $<<$ dp$[$i$][$j$]<<""$;

$\}$

cout $<<$ endl;

$\}$

$\}$

$//$ Function to find the longest common substring

string longestCommonSubstring$($string str$1,$ string str$2)\{$

int n $=$ str$1.$length$()$;

int m $=$ str$2.$length$()$;

vector$>$ dp$($n $+1,$ vector$($m $+1,0))$;

int maxLength $=0$;

int endIndex $=0$;

$//$ Fill the dynamic programming table

for $($int i $=1$; i $<=$ n; i$++)\{$

for $($int j $=1$; j $<=$ m; j$++)\{$

if $($str$1[$i $-1]==$ str$2[$j $-1])\{$

dp$[$i$][$j$]=$ dp$[$i $-1][$j $-1]+1$;

if $($dp$[$i$][$j$]>$ maxLength$)\{$

maxLength $=$ dp$[$i$][$j$]$;

endIndex $=$ i;

$\}$

$\}$ else $\{$

dp$[$i$][$j$]=0$;

$\}$

$\}$

$\}$

printDPTable$($dp$,$ str$1,$ str$2)$; $//$ Print the DP table

return str$1.$substr$($endIndex $-$ maxLength, maxLength$)$;

$\}$

int main$()\{$

string str$1,$ str$2$;

cout $<<$ "Enter String $1$: $"$;

cin $>>$ str$1$;

cout $<<$ "Enter String $2$: $"$;

cin $>>$ str$2$;

cout $<<$ "Input Strings:" $<<$ endl;

cout $<<$ "String $1$: $"<<$ str$1<<$ endl;

cout $<<$ "String $2$: $"<<$ str$2<<$ endl;

string result $=$ longestCommonSubstring$($str$1,$ str$2)$;

cout $<<$ "Longest Common Substring: $"<<$ result $<<$ endl;

cout $<<$ "Length: $"<<$ result.length$()<<$ endl; $//$ Output the length of the longest common substring

return $0$;

$\}$

do this code correct for the assignment $?$