The code does not work properly

[arsamigullin]

Hello. Looks like this code does not work properly. https://github.com/stevenhalim/cpbook-code/blob/a49dd077cbaceb9e69b8630104dedc4645187065/ch6/string_alignment.py#L1 Consider this example A = "horse" B = "ros"

Actual result: table[n][m] outputs 1

Expected result: table[n][m] should output 3

[stevenhalim]

Hi arsamigullin

Recheck again,

for, assuming match = +2 points and mismatch/insert/delete are all -1 point

A = "horse" B = "ros"

becomes

A = "horse" B = "ros" -1 +2 -1 +2 -1 = 1 point, not 3 points

so the code is correct.

Regards,

Steven Halim (Dr.) Senior Lecturer School of Computing, National University of Singapore http://www.comp.nus.edu.sg/~stevenha IOI 2020 (https://ioi2020.sg/) and 2021 (http://ioi2021.sg/) Deputy Director https://visualgo.net and https://cpbook.net (CP4 is out)

On Thu, Jul 30, 2020 at 2:50 PM arsamigullin notifications@github.com wrote:

Hello. Looks like this code does not work properly.

https://github.com/stevenhalim/cpbook-code/blob/a49dd077cbaceb9e69b8630104dedc4645187065/ch6/string_alignment.py#L1 Consider this example A = "horse" B = "ros"

Actual result: table[n][m] outputs 1

Expected result: table[n][m] should output 3

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/stevenhalim/cpbook-code/issues/72, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABIDWOEIHVF663BEWN2WD5DR6EJZ3ANCNFSM4PNADKNQ .

[arsamigullin]

Thanks for your explanation. In Competitive Programming 4 (Book2) on page 329 it is said: "The String Alignment (or Edit Distance) problem is defined as follows: Align two strings A with B with the maximum alignment score (or minimum number of edit operations)"

Thought that alignment score and number of edit operations have the same meaning. Looks like I was wrong

[stevenhalim]

the default is Align two strings A with B with the maximum alignment score with match given +2 and insert/mismatch/delete = -1 (these scores are adjustable)

ok, I ignore this issue :)

Regards,

Steven Halim (Dr.) Senior Lecturer School of Computing, National University of Singapore http://www.comp.nus.edu.sg/~stevenha IOI 2020 (https://ioi2020.sg/) and 2021 (http://ioi2021.sg/) Deputy Director https://visualgo.net and https://cpbook.net (CP4 is out)

On Thu, Jul 30, 2020 at 5:03 PM arsamigullin notifications@github.com wrote:

Thanks for your explanation. In Competitive Programming 4 (Book2) on page 329 it is said: "The String Alignment (or Edit Distance) problem is defined as follows: Align two strings A with B with the maximum alignment score (or minimum number of edit operations)"

Thought that alignment score and number of edit operations have the same meaning. Looks like I was wrong

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/stevenhalim/cpbook-code/issues/72#issuecomment-666244526, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABIDWOGU6O5CA6RG2R4FF3TR6EZNTANCNFSM4PNADKNQ .

[arsamigullin]

Yup, closed this ticket, thank you