Algorithms and Data Structures Given two strings X and Y, a third string Z is a

Question

Algorithms and Data Structures

Given two strings X and Y, a third string Z is a common superstring of X and Y if X and Y are both subsequences of Z. (Example: if X = sos and Y = soft, then Z = sosft is a common superstring of X and Y.) Design a dynamic programming algorithm which, given as input two strings X and Y, returns the length of the shortest common superstring (SCS) of X and Y. Specifically, you have to write a recurrence relation l(i, j) = |SCS(X_i, Y_j)| that defines the length of a shortest common superstring of X_i and Y_j, and the pseudocode. The algorithm, which has to return l(n, m), must run in time theta(n middot m), where n = |X| and m = |Y|.

Explanation / Answer

Answer:

given;

1(i.j)=|scs(Xi,Yj)| defines the lenth of a SHORTEST COMMON SUPER STRING of Xi and Yi

Reccurence relation;

1(i,j)={l(i-1,j-1)if Xi=Yj

max l((i,j-1,l(i-1,j)}if xi#yj

Condition;(i,j)=0 if i is o 0 or j is 0

pseudocode to find lcs (x,y):

m=|X|\ x lenth

n=|Y|\ Y lenth

for i=1 to m do

1[i,0]=0

for j =1 to n do

1[0,j]=0

for i =1 to m and j=1to n do

if(Xi=Yj)

1[i,j]=1i-1,j-1]+1;

else if(1([i-1,j]>1[i,j-1])

1[i,j]=1[i-1,j];|

else

1[i,j]=1[i,j-1]

return 1[m,n]

pseudocode to find SCS:

M=|X|;//x length

n=|Y| //Y LENGTH

len=lcs(X,Y) //call lcs(X,Y) to find the common subsequence

return(m+n-len)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.