首页 > 试题广场 >

字符串联想

[编程题]字符串联想

热度指数：112 时间限制：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

算法知识视频讲解

Italink

#include <iostream>
#include <string>
#include <regex>
#include <set>
using namespace std;
struct cmp{
    bool operator()(const string& a,const string& b) const {
        return a.size() != b.size() ? a.size() < b.size() : a < b;
    }
};
int main() {
    int n, k;
    string str,record;
    char type;
    set<string, cmp> match;
    cin >> n >> k >> str;
    for (int i = 0; i < n; i++) {
        cin >> type;
        if (type == 'A') {
            cin >> record;
            if(regex_search(record, regex(str)))
                match.insert(record);
        }
        else {
            cout << "P:" << endl;
            int output = 0;
            for (const string& s : match) {
                cout << s << endl;
                if (++output==k)
                    break;
            }
        }
    }
    return 0;
}

发表于 2020-06-04 13:43:06 回复(0)