OJ Board

Posted: **Sun Jan 20, 2008 11:23 am**

Who can give some hints about the algorithm?

Posted: **Sun Jan 20, 2008 9:00 pm**

You can apply dp. To be more specific you can use LCS (with minor changes).
But I still dont know whether the judge data is present or not (for this problem).

Posted: **Mon Jan 21, 2008 3:51 am**

Excuse me for the newbiesness, I know DP means Dynamic programming, but what is LCS?

I'm I sorry if it this a stupid question, I just want to learn.

Posted: **Mon Jan 21, 2008 10:02 am**

andmej wrote:what is LCS?

Longest Common Substring (or Subsequence).

Posted: **Mon Jan 21, 2008 10:09 am**

Jan wrote:You can apply dp. To be more specific you can use LCS (with minor changes).

You mean, for each given word, calculate its penalty with each word in the dictionary?

Posted: **Mon Jan 21, 2008 7:15 pm**

ImLazy wrote:You mean, for each given word, calculate its penalty with each word in the dictionary?

Yes.

Posted: **Tue Jan 22, 2008 5:26 pm**

Jan wrote:But I still don't know whether the judge data is present or not (for this problem).

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.

Posted: **Wed Jan 30, 2008 4:01 pm**

What a pity! This seemed a very interesting problem. I've been waiting long for a spelling correction problem in order to apply the Levenshtein Distance algorithm efficiently, but in this one anyone can get AC with an empty main function

Posted: **Thu May 01, 2014 1:04 am**

I created a dataset and emailed the admins.

Posted: **Tue Jul 29, 2014 8:42 pm**

This has been changed to a multiple input problem.
If you get PE, make sure you copy all whitespace from the input to the output. It looks there are now extra whitespace characters between words or at the beginning or end of a line.

Posted: **Mon Aug 04, 2014 10:37 pm**

Input:

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

AC output:

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

Posted: **Sat Nov 08, 2014 9:57 am**

Copying and pasting the sample input seems to omit the newline between cases. Here's the correct version of the sample input

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

OJ Board

963 - Spelling Corrector

963 - Spelling Corrector

Re: 963 - Spelling Corrector

Re: 963 - Spelling Corrector

Re: 963 - Spelling Corrector

Re: 963 - Spelling Corrector