首页 > 试题广场 >

字符串联想

[编程题]字符串联想
  • 热度指数：128 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
字符串联想是一个被广泛用于搜索引擎/输入法的功能。联想算法根据一定规则，计算出与待匹配字符串最接近的若干个联想结果。聪明的ttt觉得这功能很好，希望刚入职的lhy也实现一个简单的联想算法。

ttt：客户端将提供一个最优匹配结果数k，一个待匹配字符串，和若干个命令。希望你能实现一个算法，它实现两种操作：
A: 增加一项搜索记录
 P: 打印当前的k个最优匹配结果

我们规定每个匹配记录（record）需满足：record中存在至少一个与s完全匹配的子串。
并规定，若满足下列条件，则称record a是比record b更好的匹配记录
1.record a长度短于record b
2.长度相同，record a的字典序小于record b

这可把热爱摸鱼的lhy难倒了。为了帮lhy保住工作，和ttt一样聪明的你能帮帮lhy吗？

输入描述:
输入数据包含n + 3行每一组数据由三行组成
第一行：n
第二行：k
第三行：s
第四行~n+3行：
[A record] 或 [P]

n: 需执行的总命令数 (n < 10000)k：需要输出的总匹配记录数目（0 <k <= n）s：待匹配字符串 (0 < length < 100)A record: 增加一项record, 记录和A由空格分隔P: 打印当前的k个最优匹配结果
输入数据保证每条字符串长度 (0 < length < 100)，且仅由小写ANSI字符组成


输出描述:
每次P命令执行后，输出
P:
k行数据（不允许有重复数据，相同的看做同一条数据）。

不足k行则输出所有符合题干条件的记录。
输出顺序需按提干条件由优先级高->低顺序排列
示例1

输入

6
3
wps
A ttt.smart
A lhy.stupid.wps
P
A lhy.stupid.wps
A wps.cn
P

输出

P:
lhy.stupid.wps
P:
wps.cn
lhy.stupid.wps
示例2

输入

4
1
ttt
P
A tttnba
A ttttql
P

输出

P:
P:
tttnba

备注:
保证所有查询的输出结果加在一起字符总长度不超过5×106
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 iOS工程师 金山WPS 2020
来自：金山办公2020校招i...
上传者：小小
难度：
1条回答 3043浏览

热门推荐

通过挑战的用户

相关试题

字符串联想

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号