[Help] A String Problem Solved By DP + Aho?

Revision en1, by Libraion, 2021-09-24 05:18:03

Given a string $$$S (|S| \le 100)$$$ and $$$n (n \le 1000)$$$ strings $$$T_1, T_2, \dots, T_n (|T_i| \le 30)$$$. Each string $$$T_i$$$ has a corresponding point $$$p_i (1 \le p_i \le 10000)$$$.

You can do the following operation any number of times (until you cannot choose any substring): Choose a substring in $$$S$$$ that is equal to one of $$$T_i$$$, delete that substring in $$$S$$$, you get $$$p_i$$$ points and the remaining characters of $$$S$$$ concatenate.

What is the maximum points you can get by doing the operations?

Sample input

I was thinking about a solution using DP and Aho Corasick.

Specifically, let $$$dp(i, j) = $$$ the maximum points you can get with the first $$$i$$$ characters of $$$S$$$ and you are standing at node $$$j$$$ in the Trie after doing some operations.

But I came across a problem. When we move from $$$dp(i, j)$$$ to $$$dp(i + 1, k)$$$, if we jump from node $$$j$$$ to node $$$k$$$ with suffix link, we lost some information of the prefix that we haven't used in any operation yet.

Could you guys suggest any alternatives?

Thanks in advance.


  Rev. Lang. By When Δ Comment
en1 English Libraion 2021-09-24 05:18:03 1272 Initial revision (published)