Ajay Kumar Ojha
String Obsession
Problem Description
Who knows the reason for why little Meera is so obsessed with strings and loves to spend her time analyzing them!?
Meera has an everlasting passion for strings. One day, she took a string (let us call it the main string) along with some substrings and decided to remove as many substrings from the main string as possible. Whenever a part is removed, the remaining portions of the string are joined together. For example, if the main string is "hello" and "el" is removed, it becomes "hlo." Note that she can remove one substring only once from the string.
Given the main string and the substrings, determine and print the maximum number of substrings that can be removed.
Constraints
1 <= length of main string <= 55
1 <= length of each substring <= 15
Both main and substrings will be having only lower-case alphabets only.
Input
First line consists of N, denoting the total number of substrings.
Next line consists of N space separated substrings.
Last line consists of the main string.
Output
Print a single integer denoting the maximum number of substrings that can be removed.
Time Limit (secs)
1
Examples
Example 1
Input
6
hd el llo wor ell lds
helloworlds
Output
4
Explanation
Given main string is - helloworlds
Remove llo, the string becomes heworlds
Remove wor, the string becomes helds
Remove el, the string becomes hds
Remove hd, the string becomes s. One cannot remove anything further.
Hence the maximum number of substrings we can remove is 4, print 4 as output.
Example 2
Input
7
ggc rm oo le glh oog ec
googlechrome
Output
3
Explanation
Given main string is - googlechrome
Remove oo, the string becomes gglechrome
Remove le, the string becomes ggchrome
Remove ggc, the string becomes hrome. One cannot remove anything further.
Second possibility can also be - removing ec,glh,oo resulting in grome, further reduction is impossible. In this case also only 3 substrings have been removed.
Hence the maximum number of substrings we can remove is 3, hence print 3 as output.