单点时限: 2.0 sec
内存限制: 256 MB
一个字符串 $s$ (由英文字母及-组成)，包含若干个英语单词，但单词之间缺少了空格。根据给定的词典，把字符串中的单词分割开。
其中一种简单的方法叫做最大分词法，其基本思想是优先考虑把字符串首部最长的单词切割出来。
算法流程如下(假设词典中最长词长为 $L$ 个字符)：
对字符串 $s[0…n]$，检查子串 $s[0…L-1]$ 是否在词典中，如果在的话，把该子串切割出来，构成一个词；如果不在，缩减子串长度，依次检查 $s[0…L-1]$, $s[0…L-2]$, …, $s[0,1]$ 是否可以构成一个词，直到串首能分割出一个合法单词，或待检查的子串只包含一个字符 $s[0]$，则将该字符分割出来。对剩余子串重复上述过程，直至完成对所有字符的分割。
例如，假设词典中包含4个单词：$a, an, and, dog$。
待分割字符串为 $annaandog$ ，分割结果为：$an$ $n$ $a$ $and$ $o$ $g$ 。
( 注：该算法不能保证分词结果完全正确或所分出的单词都在词典中。)
输入的第一行包含一个整数 $n (1 \leq n \leq 4000)$，代表词典中的词数。
接下来 $n$ 行，每行一个单词 (只包含英文字母和 -，区分大小写， $1 \leq 单词长度 \leq 14$)。
接下来一行包含一个待分割字符串 $s$, $(1 \leq s的长度 \leq 5000)$。
在一行中输出分词结果，两个单词之间用一个空格分开，最后一个单词后没有空格。行末输出一个换行符。
4 a an dog and annaandog
an n a and o g
6 a an e-mail abandon absolute absolutely abandonabsolutely
abandon absolutely
3 a an e-mail ane-mail
an e-mail