963 - Spelling Corrector
Posted: Sun Jan 20, 2008 11:23 am
Who can give some hints about the algorithm?
The UVa Online Judge board
https://uva.onlinejudge.org/board/
https://uva.onlinejudge.org/board/viewtopic.php?f=34&t=27907
Longest Common Substring (or Subsequence).andmej wrote:what is LCS?
You mean, for each given word, calculate its penalty with each word in the dictionary?Jan wrote:You can apply dp. To be more specific you can use LCS (with minor changes).
Yes.ImLazy wrote:You mean, for each given word, calculate its penalty with each word in the dictionary?
It seems like you said. I kept getting Runtime Error. But when I submitted a code with only an empty main function, it was Accepted. There is quite something wrong with the test data of this problem.Jan wrote:But I still don't know whether the judge data is present or not (for this problem).
Code: Select all
49
abfuz
b
bttl
ceqhywnq
d
daqlkcbni
dpxf
ezcxk
fgsuahz
fsgi
gsqqhegi
kjvas
knrt
lbubud
ll
lolzbcbf
mgfbby
moy
mq
mtmfn
n
naofqayjk
ndb
nrp
oc
pu
pzn
q
qkh
qmtrhocg
rkkorjmbp
rmgoaza
rqbyse
rqtnsn
rxxfxw
s
smmr
szwsccr
t
ulggietw
uyfmxw
vlwt
vuczjzg
xryo
yaswa
ye
zi
zmxopmods
ztsq
51
i xszama rpqlrrxs petdli knkzjpjv bu pwkgldtcu wuib lmx wmavv
gshhowwkj xmy i yeyztk rak ahbsov vmyu hawvaxdp knwdzkubu c
d paynm jlfjha gf epqavskrt txkyuzz onsxyx hz q wuyowtg
mapgz etbfppv ptgydhvt tnoh jquvskbrj n peckmtgu lcogqhv q pgb
alo wyhjp nczgi zvwnbou w clt xtqnnnlwy kndjt fskdhltb pnlagpyc
lrwzo
Code: Select all
zi s nrp d nrp b pu b ll mq
s moy zi ye b b moy yaswa ndb oc
d pzn ll b knrt t moy zi q t
pzn b d n qkh n pu q q b
ll ye zi b b t n knrt ndb nrp
xryo
Code: Select all
5
ate
carrot
rabbit
the
white
6
the white rabit ate ate carott
20
a
abbey
adapted
ago
almost
but
clumsy
had
he
joined
living
manuel
monk
not
of
that
the
to
way
year
22
the clumsy momk manuel had joined the abey almost a
year ago but he had not adapted to that way
of leaving