爱提问题的导师

TimeLimit:3000MS  MemoryLimit:512MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

你们好,我是一名来自QWERTYUIOP大学的一名毕业生,

现在我正在面临一个巨大的难题,在毕业设计中,我的导师要求我完成一个任务,

他的要求是这样的:

假设我们有一个给定的字符串s和一个目标字符串t,

首先,我们要将字符串中的单词按照分隔符(",/.-")[注意都是英文字符]来分割单词,

比如字符串hallo-world,we/are.winners,我们就可以将其分割为hallo world we are winners 5个单词

现在我们对任意的一个单词定义一个相似度为d(x),

d(x)表示为单词与目标字符串中最长的相同子串长度

比如:

两个单词:ab,b

目标字符串:bb

单词与目标字符串的相似度为:d(ab) = 1, d(b) = 1,因为单词ab与bb有一个相同的子串b长度为1,同时b与bb也有一个相同的子串长度为1,

现在,导师会给我一个很长的字符串和一个目标字符串,

他希望我能在3s(由于oj的时间是累加的所以开放到3s)的时间内告诉他有多少个单词与目标字符串相似度最大,

并把这些单词按照顺序告诉他,请你们帮帮我!

Input

第一行输入一个字符串(1 <= s.size() <= 2e4),保证字符串中的被分隔符分隔的单词长度不超过6

第二行输入一个字符串为需要的匹配串(1 <= t.size() <= 1e3)

保证字母都是小写字母

Output

第一行输出一个数字,表示相似单词的个数

接下来每行输出一个字符串, 代表相似单词,

若不存在相似字符串(即所有单词与目标字符串的相似度都为0),则输出None

SampleInput
样例1
ab,b,b
bb

样例2
hello,world
zxc
SampleOutput
样例1
3
ab
b
b

样例2
None
Submit
题目统计信息详细
总AC数8
通过人数2
尝试人数4
总提交量26
AC率7.69%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
作者

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: