kalimm's blog

IX Zhautykov Olympiad : [Problem G] Round Words
By kalimm, history, 11 years ago, In English

What is the lenght of largest common subsequence of two round words? In a round word there is no difference from which symbol the word starts and in which direction it is read.

lcs("algorithm", "grammar") = "grma"

1≤N≤2000

http://izho.kz/uploads/izho_2013_en_inform.pdf

Do you have any solutions? Thanks for help.

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 15  
Vote: I like it -17 Vote: I do not like it 
substr(firstPost, len)
x[i][j] = lcm(a.substr(0, i), b.substr(0, j)) // can be built by easy n * n DP
y[i][j] = lcm(a.substr(n - i, i), b.substr(n - j, j)) 
ans = min(ans, x[i][j] + y[n - i][n - j]) for each i, j; 0 <= i, j <= n

Second table Y can be found by the same DP like first one, but for reversed strings a and b.
UPD: "Beware of bugs in the above code; I have only proved it correct, not tried it". Donald Knuth(c)
there are at least two bugs: lcm — lcs, min — max.

→ Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +26 Vote: I do not like it

Maybe this could help you :D

→ Reply