| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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!!
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.
Thanks a lot. but i want to know what ac node record? Record whether it visited by some virus??
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.
额。。那个可以用中文不？ac节点是表示字符匹配的状态呗？那么假设题意是对于任意virus，都不能以子串的形式出现，那么我对应ac自动机里trie树上每个节点应该存什么？