Jump to content
Main menu
Main menu
move to sidebar
hide
Navigation
Main page
Contents
Current events
Random article
About Wikipedia
Contact us
Donate
Contribute
Help
Learn to edit
Community portal
Recent changes
Upload file
Search
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
User
:
Nils Grimsmo/LCS2
Add languages
User page
Talk
English
Read
Edit
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Edit
View history
General
What links here
Related changes
User contributions
User logs
View user groups
Upload file
Special pages
Permanent link
Page information
Get shortened URL
Download QR code
Print/export
Download as PDF
Printable version
From Wikipedia, the free encyclopedia
<
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]\;}
Toggle limited content width
![{\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)
