String Segmentation Problem

Given a string s and a dictionary of words, determine whether s can be segmented into a sequence of one or more dictionary words.

You need to decide if there exists a valid segmentation such that, if we define a boolean array \(dp\) of length \(n+1\) (where \(n\) is the length of s), then

\[ dp[i] = \begin{cases} true, & \text{if } \exists\; j,\; 0 \le j < i \text{ such that } dp[j] \text{ is true and } s[j:i] \in \text{dictionary}\\ false, & \text{otherwise.} \end{cases} \]

The answer is based on the value of \(dp[n]\), and you should output "true" if segmentation is possible, otherwise "false".

inputFormat

The input is read from stdin and consists of multiple lines:

1. The first line contains an integer \(m\), the number of words in the dictionary.
2. The next \(m\) lines each contain one word.
3. The last line contains the string \(s\) to be segmented.

outputFormat

The output is a single line to stdout containing either "true" if the string can be segmented into one or more dictionary words, or "false" otherwise.

5
apple
pen
applepen
pine
pineapple
pineapplepenapple

true