User
:
Nils Grimsmo/LCS2
From WikiProjectMed
<
User:Nils Grimsmo
Jump to navigation
Jump to search
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]\;}
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Log in
Namespaces
User page
Talk
English
Views
Read
View source
View history
More
Search
Navigation
Main page
Recent changes
Random page
Donate
Donate
Projects
Wiki Project Med
Community pump
List of articles
Translation
Internet-in-a-Box
Offline app
VideoWiki
OWID
Requested images
Calculators
Tech
Common links
Import tool
Editors
Upload file
Med updater
Create redirects
Import history
Other projects
Commons
NC Commons
Tools
What links here
Related changes
Special pages
Printable version
Page information
![{\displaystyle \mathrm {C} \leftarrow \;\mathbf {array} {[0\dots m,0\dots n]}\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0371b4c71b9adbb23565d576681d328eb925cc2c)
![{\displaystyle \mathbf {if} \;X[i]=Y[j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb58f27f72bddebeee5aaf82d0c3612c1c7679da)
![{\displaystyle \mathrm {C} [i,j]\leftarrow \mathrm {C} [i-1,j-1]+1\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/693163a5fbddd286a185ce4a0eb33c5d3b93764b)
![{\displaystyle \mathrm {C} [i,j]\leftarrow \max(\mathrm {C} [i,j-1],\mathrm {C} [i-1,j])\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f30a6520d6dc146615f584ed51c57d4c8aa7b50)
![{\displaystyle \mathbf {else\;if} \;X[i]=Y[j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f2123b84d4ad482e1d9cdbd7cbf1e4676544f77)
![{\displaystyle \mathbf {return} \;{\textrm {BackTrack}}(i-1,j-1)+X[i]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fda4b12c219b0977d1ac0da7749b2440734b399)
![{\displaystyle \mathbf {if} \;\mathrm {C} [i,j-1]>\mathrm {C} [i-1,j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6419998e45da7b449be82d6c04ca674cc7d7a06)
![{\displaystyle {\textbf {else}}\;{\textbf {if}}\;X[i]=Y[j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76836c13af022b6bd721deb2964d83400e5bbb33)
![{\displaystyle {\textbf {return}}\;\{Z+X[i]\;|\;Z\in {\textrm {BackTrackAll}}(i-1,j-1)])\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79af00b10abd64691ad800e5129068cf7bd39c6a)
![{\displaystyle {\textbf {if}}\;{\textrm {C}}[i,j-1]\geq {\textrm {C}}[i-1,j]:\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61401eb0875c6dc9d2b73773bbd7f358a5ed336e)
![{\displaystyle {\textbf {if}}\;{\textrm {C}}[i-1,j]\geq {\textrm {C}}[i,j-1]:\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d133b685a802d8a1051c0eecb4db9a7b4f6e2d1)
![{\displaystyle {\textbf {if}}\;i>0\;{\textbf {and}}\;j>0\;{\textbf {and}}\;X[i]=Y[j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b08eefe3f64f22b722b95d8f1f8ab4388129c163)
![{\displaystyle {\textbf {print}}\;{\textrm {''}}\;\;{\textrm {''}}+X[i]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25bc05a39e511d40d2a6cf66f012fd128dc9b029)
![{\displaystyle {\textbf {if}}\;j>0\;{\textbf {and}}\;(i=0\;{\textbf {or}}\;{\textrm {C}}[i][j-1]\geq {\textrm {C}}[i-1][j])\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d23c4ee843ad94cf6b87ed60bb7c97b81272f107)
![{\displaystyle {\textbf {print}}\;{\textrm {''+''}}+Y[j]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49a08207063d935b9354dc3d1af85e7dd1e9bf78)
![{\displaystyle {\textbf {else}}\;{\textbf {if}}\;i>0\;{\textbf {and}}\;(j=0\;{\textbf {or}}\;{\textrm {C}}[i][j-1]<{\textrm {C}}[i-1][j])\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed001e4ae82eebe44eac5f4cae066cab186805a6)
![{\displaystyle {\textbf {print}}\;{\textrm {''-''}}+X[i]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee48b6ed3d2fad0baf6efef5d4180c5d0c1eb286)