#CT0107. 最大分词法

最大分词法

题目描述

一个字符串 ss (由英文字母组成),包含若干个英语单词,但单词之间缺少了空格。根据给定的词典,把字符串中的单词分割开。

其中一种简单的方法叫做最大分词法,其基本思想是优先考虑把字符串首部最长的单词切割出来。

算法流程如下(假设词典中最长词长为 LL 个字符):

对字符串 s[0n]s[0\dots n],检查子串 s[0L1]s[0\dots L-1] 是否在词典中,如果在的话,把该子串切割出来,构成一个词;如果不在,缩减子串长度,依次检查 s[0L1]s[0\dots L-1], s[0L2]s[0\dots L-2], …,s[01]s[0\dots 1] 是否可以构成一个词,直到串首能分割出一个合法单词,或待检查的子串只包含一个字符 s[0]s[0],则将该字符分割出来。对剩余子串重复上述过程,直至完成对所有字符的分割。

例如,假设词典中包含 44 个单词: a,an,and,doga,an,and,dog

待分割字符串为 annaandogannaandog,分割结果为:an n a and o gan\ n\ a\ and\ o\ g

( 注:很显然,该算法是一种贪心,不能保证分词结果完全正确或所分出的单词都在词典中。赛后你也可以思考一种做法,实现只要句子是完全可分的,则一定能找到完全分词的方案)

输入格式

输入的第一行包含一个整数 n(1n4000)n(1\leq n \leq 4000),代表词典中的词数。

接下来 nn 行,每行一个单词 ww (只包含小写英文字母, 1w141\leq |w| \leq 14)。

接下来一行包含一个待分割字符串 s(1s5000)s(1\leq |s| \leq 5000)

输出格式

在一行中输出分词结果,两个单词之间用一个空格分开,最后一个单词后没有空格。行末输出一个换行符。

测试样例

4
a
an
dog
and
annaandog
an n a and o g
6
a
an
email
abandon
absolute
absolutely
abandonabsolutely
abandon absolutely
3
a
an
email
anemail
an email