Background

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.

Problem Description

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?

Input Format

• 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 Format

Output one integer, the maximum number of segments.

asdsd
3
as
sd
ds

2

Hint

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