Maximum Valid String Segmentation

You are given a string S and a dictionary of words. You are allowed to split the string into several contiguous substrings. However, each substring must contain at least one word from the given dictionary (i.e. one of the dictionary words appears as a contiguous substring within that segment).

Your task is to determine the maximum number of substrings into which the string can be split so that every piece is valid. If it is not possible to split the string so that every piece satisfies the condition, output 0.

Note: The dictionary words and the input string consist of lowercase English letters.

Algorithm Hint:

Let S be the input string of length L.
Define an array \(dp[0..L]\) where \(dp[i]\) denotes the maximum number of valid segments from the beginning of S up to index i. Initialize \(dp[0]=0\) and for all other indices, \(dp[i]=-\infty\) (or an impossible flag).
For each index \(i\) from 1 to L:
  For each \(j\) from 0 to i-1:
    If \(dp[j]\) is valid and the substring \(S[j:i]\) contains one of the dictionary words as a substring, then update:
    \[
dp[i] = max(dp[i], dp[j]+1)\]
Finally, the answer is \(dp[L]\) (if no valid segmentation exists, output 0).

The condition for a substring \(T\) to be valid is:

[ \exists w \in Dictionary \quad \text{such that} \quad w \subseteq T ]

inputFormat

The input is given via standard input and has the following format:

Line 1: A non-empty string S
Line 2: An integer N representing the number of words in the dictionary
Next N lines: Each line contains a non-empty dictionary word

It is guaranteed that S and all dictionary words consist of lowercase English letters.

outputFormat

Output a single integer representing the maximum number of substrings into which S can be split such that each substring contains at least one word from the dictionary. If no valid segmentation exists, output 0.

sample

abcvsdaas
3
abc
vs
aas

3