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

Code Forces Round 201 B Lucky Common Subsequence strongly question
Автор luyuncheng, 13 лет назад, По-английски

For this question：codeforces 201B Lucky Common Subsequence。 it ask us just one virus so we can use kmp + dp to solve this question。

but i have a question that if ask us more than one virus what should i do？？ i have an ideal just use Aho-Corasick automaton to get fail array but i do not know how to set dp array？

Can anyone help me ?

Thanks in advance!!

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

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Assign an index to each AC node and represent the fail transitions accordingly.

Instead of having a DP array dp[s1 length][s2 length][virus length], you'll have dp[s1][s2][y] and it is calculated using dp[s1-1][s2][y], dp[s1][s2-1][y], and dp[s1-1][s2-1][x] for all x that have a fail transition from AC node y to AC node x.

→ Ответить