#CT0107. 最大分词法
最大分词法
题目描述
一个字符串 (由英文字母组成),包含若干个英语单词,但单词之间缺少了空格。根据给定的词典,把字符串中的单词分割开。
其中一种简单的方法叫做最大分词法,其基本思想是优先考虑把字符串首部最长的单词切割出来。
算法流程如下(假设词典中最长词长为 个字符):
对字符串 ,检查子串 是否在词典中,如果在的话,把该子串切割出来,构成一个词;如果不在,缩减子串长度,依次检查 , , …, 是否可以构成一个词,直到串首能分割出一个合法单词,或待检查的子串只包含一个字符 ,则将该字符分割出来。对剩余子串重复上述过程,直至完成对所有字符的分割。
例如,假设词典中包含 个单词: 。
待分割字符串为 ,分割结果为:。
( 注:很显然,该算法是一种贪心,不能保证分词结果完全正确或所分出的单词都在词典中。赛后你也可以思考一种做法,实现只要句子是完全可分的,则一定能找到完全分词的方案)
输入格式
输入的第一行包含一个整数 ,代表词典中的词数。
接下来 行,每行一个单词 (只包含小写英文字母, )。
接下来一行包含一个待分割字符串 。
输出格式
在一行中输出分词结果,两个单词之间用一个空格分开,最后一个单词后没有空格。行末输出一个换行符。
测试样例
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