Paul is happy today because he has created a simple Dynamic Programming solution that will allow him to split a string without spaces into recognizable words. (Ex. Split "helloworld" into "hello" and "world") This will finally help resolve this! Since Paul wants to share this discovery, he has decided to create a problem on it.
The first line of input contains an integer \(n\). \((30 \le n \le 200)\)
The next \(n\) lines contain an alpha-numeric string, a "word".
The next line contains a string, for your submission to split into words.
Output the number of possible ways the string can be splitted into given words.
6
hello
people
hell
o
peo
ple
hellopeople
4
"hellopeople" can be split in four ways:
1. "hello", and "people"
2. "hell", "o", and "people"
3. "hello", "peo", and "ple"
4. "hell", "o", "peo", and "ple"