你们好,我是一名来自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)的时间内告诉他有多少个单词与目标字符串相似度最大,
并把这些单词按照顺序告诉他,请你们帮帮我!
第一行输入一个字符串(1 <= s.size() <= 2e4),保证字符串中的被分隔符分隔的单词长度不超过6
第二行输入一个字符串为需要的匹配串(1 <= t.size() <= 1e3)
保证字母都是小写字母
第一行输出一个数字,表示相似单词的个数
接下来每行输出一个字符串, 代表相似单词,
若不存在相似字符串(即所有单词与目标字符串的相似度都为0),则输出None
样例1 ab,b,b bb 样例2 hello,world zxc
样例1 3 ab b b 样例2 None