Scribd
Upload
22 views1 page

LCS Algorithm Flowchart

The document outlines a flowchart for calculating the Longest Common Subsequence (LCS) between two sequences, x and y. It details the initialization of the LCS table and the iterative process of comparing elements from both sequences to fill the table. The final output is the length of the LCS derived from the completed table.

Uploaded by

tushar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
22 views1 page

LCS Algorithm Flowchart

The document outlines a flowchart for calculating the Longest Common Subsequence (LCS) between two sequences, x and y. It details the initialization of the LCS table and the iterative process of comparing elements from both sequences to fill the table. The final output is the length of the LCS derived from the completed table.

Uploaded by

tushar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

digraph {

S [label=Start shape=oval]
I1 [label="x & y be two given sequences" shape=parallelogram]
I2 [label="Initialize LCS table of size
(len(x)+1) x (len(y)+1)" shape=parallelogram]
I3 [label="Set LCS[0][j] = 0
Set LCS[i][0] = 0" shape=parallelogram]
L [label="Loop i from 1 to len(x)
Loop j from 1 to len(y)" shape=diamond]
C [label="Compare x[i] & y[j]" shape=diamond]
T [label="LCS[i][j] = 1 + LCS[i-1][j-1]" shape=rectangle]
F [label="LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])" shape=rectangle]
R [label="Return LCS[len(x)][len(y)]" shape=parallelogram]
E [label=End shape=oval]
S -> I1
I1 -> I2
I2 -> I3
I3 -> L
L -> C [label="For each i, j"]
C -> T [label="If x[i] == y[j]" style=solid]
C -> F [label=Else style=dashed]
T -> L [label="Next iteration"]
F -> L [label="Next iteration"]
L -> R [label="Loop complete" style=dashed]
R -> E
}

You might also like