P2031 Mind Master: Split the String

Alright, time for the usual prelude. Voice-over: At last, after two rounds of rigorous selection, our open audition has come to an end. Now we enter the round-robin stage. There are four matches in the round-robin, and the top $16$ scorers advance to the showdown. If scores are tied, rank by time used; if we still cannot determine the top $16$, truncate. Welcome to the comprehensive arts-and-knowledge show “Play Happily, Win Easily,” proudly presented by Luogu TV. I am LUWM. Learn programming? Choose Luogu. Many thanks to Luogu Online Judge for its strong support. Now, let’s invite $10$ contestants to the stage; the big screen will display the problem.

You are given a string. You may split this string into segments. For example, `abcvsdaas` can be split as `abc|vs|d|aas`. You are also given a dictionary. Each segment after splitting must contain at least one word from the dictionary as a substring. What is the maximum number of segments you can obtain?

- The first line contains a string. - The second line contains a positive integer $N$, the number of strings in the dictionary. - The next $N$ lines each contain a string $A_i$, representing a dictionary string.

Output one integer, the maximum number of segments.

Special case: If the original string cannot be split, output $0$. Constraints: For $20\%$ of the testdata, $1\leq |s| \leq 50, 1\leq n\leq 50$. For $100\%$ of the testdata, $1\leq |A_i| \leq |s|\leq 300, 1\leq N\leq 500$. Here, $|s|, |A_i|$ denote the lengths of string $s$ and $A_i$. Translated by ChatGPT 5