luyuncheng's blog

Code Forces Round 201 B Lucky Common Subsequence strongly question
By luyuncheng, 11 years ago, In English

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!!

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot. but i want to know what ac node record? Record whether it visited by some virus??

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ac node is just the stage of string matching. The number of ac nodes is at most (sum of all lengths of accept strings). In this case you need to build the automaton with multiple 'accept' stages.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        额。。那个可以用中文不？ac节点是表示字符匹配的状态呗？那么假设题意是对于任意virus，都不能以子串的形式出现，那么我对应ac自动机里trie树上每个节点应该存什么？

        → Reply