Блог пользователя kalimm

IX Zhautykov Olympiad : [Problem G] Round Words
Автор kalimm, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 15   Проголосовать: нравится -17 Проголосовать: не нравится 
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.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

Maybe this could help you :D

→ Ответить