Home
Random
Nearby
Log in
Settings
Donate
About Wikipedia
Disclaimers
Search
User
:
Nils Grimsmo/LCS2
User page
Talk
Language
Watch
Edit
<
User:Nils Grimsmo
L
C
S
(
X
,
Y
)
{\displaystyle \mathrm {LCS} (X,Y)\;}
C
←
a
r
r
a
y
[
0
…
m
,
0
…
n
]
{\displaystyle \mathrm {C} \leftarrow \;\mathbf {array} {[0\dots m,0\dots n]}\;}
f
o
r
i
←
1
…
m
{\displaystyle \mathbf {for} \;i\leftarrow 1\dots m\;}
f
o
r
j
←
1
…
n
{\displaystyle \mathbf {for} \;j\leftarrow 1\dots n\;}
i
f
X
[
i
]
=
Y
[
j
]
{\displaystyle \mathbf {if} \;X[i]=Y[j]\;}
C
[
i
,
j
]
←
C
[
i
−
1
,
j
−
1
]
+
1
{\displaystyle \mathrm {C} [i,j]\leftarrow \mathrm {C} [i-1,j-1]+1\;}
e
l
s
e
{\displaystyle \mathbf {else} }
C
[
i
,
j
]
←
max
(
C
[
i
,
j
−
1
]
,
C
[
i
−
1
,
j
]
)
{\displaystyle \mathrm {C} [i,j]\leftarrow \max(\mathrm {C} [i,j-1],\mathrm {C} [i-1,j])\;}
r
e
t
u
r
n
C
{\displaystyle \mathbf {return} \;\mathrm {C} \;}
foo
BackTrack
(
i
,
j
)
{\displaystyle {\textrm {BackTrack}}(i,j)\;}
i
f
i
=
0
or
j
=
0
{\displaystyle \mathbf {if} \;i=0\;{\textbf {or}}\;j=0\;}
r
e
t
u
r
n
∅
{\displaystyle \mathbf {return} \;\emptyset \;}
e
l
s
e
i
f
X
[
i
]
=
Y
[
j
]
{\displaystyle \mathbf {else\;if} \;X[i]=Y[j]\;}
r
e
t
u
r
n
BackTrack
(
i
−
1
,
j
−
1
)
+
X
[
i
]
{\displaystyle \mathbf {return} \;{\textrm {BackTrack}}(i-1,j-1)+X[i]\;}
e
l
s
e
{\displaystyle \mathbf {else} }
i
f
C
[
i
,
j
−
1
]
>
C
[
i
−
1
,
j
]
{\displaystyle \mathbf {if} \;\mathrm {C} [i,j-1]>\mathrm {C} [i-1,j]\;}
r
e
t
u
r
n
B
a
c
k
T
r
a
c
k
(
i
,
j
−
1
)
{\displaystyle \mathbf {return} \;\mathrm {BackTrack} (i,j-1)\;}
e
l
s
e
{\displaystyle \mathbf {else} \;}
r
e
t
u
r
n
BackTrack
(
i
−
1
,
j
)
{\displaystyle \mathbf {return} \;{\textrm {BackTrack}}(i-1,j)\;}
bar
BackTrackAll
(
i
,
j
)
:
{\displaystyle {\textrm {BackTrackAll}}(i,j):\;}
if
i
=
0
or
j
=
0
{\displaystyle {\textbf {if}}\;i=0\;{\textbf {or}}\;j=0\;}
return
{
∅
}
{\displaystyle {\textbf {return}}\;\{\emptyset \}\;}
else
if
X
[
i
]
=
Y
[
j
]
{\displaystyle {\textbf {else}}\;{\textbf {if}}\;X[i]=Y[j]\;}
return
{
Z
+
X
[
i
]
|
Z
∈
BackTrackAll
(
i
−
1
,
j
−
1
)
]
)
{\displaystyle {\textbf {return}}\;\{Z+X[i]\;|\;Z\in {\textrm {BackTrackAll}}(i-1,j-1)])\;}
else
{\displaystyle {\textbf {else}}\;}
R
←
{
}
{\displaystyle R\leftarrow \{\}\;}
if
C
[
i
,
j
−
1
]
≥
C
[
i
−
1
,
j
]
:
{\displaystyle {\textbf {if}}\;{\textrm {C}}[i,j-1]\geq {\textrm {C}}[i-1,j]:\;}
R
←
R
∪
BackTrackAll
(
i
,
j
−
1
)
{\displaystyle R\leftarrow R\cup {\textrm {BackTrackAll}}(i,j-1)\;}
if
C
[
i
−
1
,
j
]
≥
C
[
i
,
j
−
1
]
:
{\displaystyle {\textbf {if}}\;{\textrm {C}}[i-1,j]\geq {\textrm {C}}[i,j-1]:\;}
R
←
R
∪
BackTrackAll
(
i
−
1
,
j
)
{\displaystyle R\leftarrow R\cup {\textrm {BackTrackAll}}(i-1,j)\;}
return
R
{\displaystyle {\textbf {return}}\;R\;}
baz
PrintDiff
(
i
,
j
)
{\displaystyle {\textrm {PrintDiff}}(i,j)\;}
if
i
>
0
and
j
>
0
and
X
[
i
]
=
Y
[
j
]
{\displaystyle {\textbf {if}}\;i>0\;{\textbf {and}}\;j>0\;{\textbf {and}}\;X[i]=Y[j]\;}
PrintDiff
(
i
−
1
,
j
−
1
)
{\displaystyle {\textrm {PrintDiff}}(i-1,j-1)\;}
print
''
''
+
X
[
i
]
{\displaystyle {\textbf {print}}\;{\textrm {''}}\;\;{\textrm {''}}+X[i]\;}
else
{\displaystyle {\textbf {else}}\;}
if
j
>
0
and
(
i
=
0
or
C
[
i
]
[
j
−
1
]
≥
C
[
i
−
1
]
[
j
]
)
{\displaystyle {\textbf {if}}\;j>0\;{\textbf {and}}\;(i=0\;{\textbf {or}}\;{\textrm {C}}[i][j-1]\geq {\textrm {C}}[i-1][j])\;}
PrintDiff
(
i
,
j
−
1
)
{\displaystyle {\textrm {PrintDiff}}(i,j-1)\;}
print
''+''
+
Y
[
j
]
{\displaystyle {\textbf {print}}\;{\textrm {''+''}}+Y[j]\;}
else
if
i
>
0
and
(
j
=
0
or
C
[
i
]
[
j
−
1
]
<
C
[
i
−
1
]
[
j
]
)
{\displaystyle {\textbf {else}}\;{\textbf {if}}\;i>0\;{\textbf {and}}\;(j=0\;{\textbf {or}}\;{\textrm {C}}[i][j-1]<{\textrm {C}}[i-1][j])\;}
PrintDiff
(
i
−
1
,
j
)
{\displaystyle {\textrm {PrintDiff}}(i-1,j)\;}
print
''-''
+
X
[
i
]
{\displaystyle {\textbf {print}}\;{\textrm {''-''}}+X[i]\;}