User:Nils Grimsmo/LCS2

From Wikipedia, the free encyclopedia

\mathrm{LCS}(X, Y)\;
\mathrm{C} \leftarrow \;\mathbf{array}{[0 \dots m,0 \dots n]}\;
\mathbf{for}\; i \leftarrow 1 \dots m\;
\mathbf{for}\; j \leftarrow 1 \dots n\;
\mathbf{if}\; X[i] = Y[j]\;
\mathrm{C}[i,j] \leftarrow \mathrm{C}[i-1,j-1] + 1\;
\mathbf{else}
\mathrm{C}[i,j] \leftarrow \max(\mathrm{C}[i,j-1], \mathrm{C}[i-1,j])\;
\mathbf{return}\; \mathrm{C}\;

foo

\textrm{BackTrack}(i, j)\;
\mathbf{if}\;i = 0 \;\textbf{or}\; j = 0\;
\mathbf{return}\; \emptyset\;
\mathbf{else\; if}\; X[i] = Y[j]\;
\mathbf{return}\;\textrm{BackTrack}(i-1, j-1) + X[i]\;
\mathbf{else}
\mathbf{if}\;\mathrm{C}[i,j-1] > \mathrm{C}[i-1,j]\;
\mathbf{return}\;\mathrm{BackTrack}(i, j-1)\;
\mathbf{else}\;
\mathbf{return}\; \textrm{BackTrack}(i-1, j)\;

bar

\textrm{BackTrackAll}(i, j):\;
\textbf{if}\; i = 0 \;\textbf{or}\; j = 0\;
\textbf{return}\; \{ \emptyset \}\;
\textbf{else}\;\textbf{if}\; X[i] = Y[j]\;
\textbf{return}\; \{Z + X[i] \;|\; Z \in \textrm{BackTrackAll}(i-1, j-1)])\;
\textbf{else}\;
R \leftarrow \{\}\;
\textbf{if}\; \textrm{C}[i,j-1] \geq \textrm{C}[i-1,j]:\;
R \leftarrow R \cup \textrm{BackTrackAll}(i, j-1)\;
\textbf{if}\; \textrm{C}[i-1,j] \geq \textrm{C}[i,j-1]:\;
R \leftarrow R \cup \textrm{BackTrackAll}(i-1, j)\;
\textbf{return}\; R\;

baz

\textrm{PrintDiff}(i, j)\;
\textbf{if}\; i > 0 \;\textbf{and}\; j > 0 \;\textbf{and}\; X[i] = Y[j]\;
\textrm{PrintDiff}(i-1, j-1)\;
\textbf{print}\; \textrm{''}\;\;\textrm{''} + X[i]\;
\textbf{else}\;
\textbf{if}\; j > 0 \;\textbf{and}\; (i = 0 \;\textbf{or}\; \textrm{C}[i][j-1] \geq \textrm{C}[i-1][j])\;
\textrm{PrintDiff}(i, j-1)\;
\textbf{print}\; \textrm{''+''} + Y[j]\;
\textbf{else}\;\textbf{if}\; i > 0 \;\textbf{and}\; (j = 0 \;\textbf{or}\; \textrm{C}[i][j-1] < \textrm{C}[i-1][j])\;
\textrm{PrintDiff}(i-1, j)\;
\textbf{print}\; \textrm{''-''} + X[i]\;