算法刷题笔记|牛客网 NC20859 兔子的名字字符串|字符串|算法|牛客网|

文章目录

1. 题目描述

1.1. Title
1.2. Time Limit
1.3. Memory Limit
1.4. Problem Description
1.5. Input
1.6. Output
1.7. Sample Input
1.8. Sample Output
1.9. Note
1.10. Source

2. 题解
3. 代码

1. 题目描述 1.1. Title
牛客网 NC20859 兔子的名字
1.2. Time Limit
C/C++ 1秒，其他语言2秒
1.3. Memory Limit
C/C++ 131072K，其他语言262144K
1.4. Problem Description
兔子发现序列的名字都是数字，实在太无聊了，于是兔子开始研究兔子的名字。
现在兔子手上有 n 个名字 Ti 和 m 个可爱词汇Sj，兔子对每一个名字 Ti 定义了一个可爱度，如果 Ti 中出现了一个可爱的单词 Sj，那么 Ti 就有 1 点可爱值，最后的总可爱值就是 Ti 的可爱度，这里的出现指 Sj 是 Ti 的子序列。
例如 abc 是 aebdc 的子序列，abc 也是 abcd 的子序列。
现在兔子想知道每一个名字的可爱度。
1.5. Input
第 1 行两个整数 n 和 m，表示名字个数和可爱词汇个数。
接下来 n 行，第 i 行是字符串 Ti ，表示兔子手里的名字。
再接下来 m 行，每行一个字符串 Sj ，表示兔子手里的可爱词汇。
1.6. Output
输出共 n 行，每行一个整数，表示每一个名字的可爱度。
1.7. Sample Input

5 3 Bunny Rabbit TuZi MianZi Sunny uny i a

1.8. Sample Output

1 2 1 2 1

1.9. Note
对于40 % 40\% 40% 的数据
1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100
对于100 % 100\% 100% 的数据
1 ≤ n ≤ 1000 ， 1 ≤ m ≤ 100 ， 1 ≤ ∣ T i ∣ ≤ 100 ， 1 ≤ ∣ S i ∣ ≤ 30 1 \le n \le 1000，1 \le m \le 100，1 \le| T_i |\le 100，1 \le|S_i|\le 30 1≤n≤1000，1≤m≤100，1≤∣Ti?∣≤100，1≤∣Si?∣≤30
|s| 表示 s 的长度请注意，字符串区分大小写。
1.10. Source
牛客网 NC20859 兔子的名字
2. 题解每读入一个模式串，遍历每个主串，对每个模式串中的字母进行依次匹配，下一次匹配的位置从上一次匹配完的位置开始，防止重复和乱序。
每个模式串中的字母都能匹配上则对其可爱度进行加一。
3. 代码

#include using namespace std; const int maxN = 1e3 + 1; string list[maxN], str; int ans[maxN] = { 0 }; bool multiMatch(string str, string pattern) { size_t locBuffer = 0; for (size_t i = 0; i < pattern.size(); i++) { // 从上一个位置查找 locBuffer = str.find(pattern[i], locBuffer); // 如果没有找到 if (locBuffer == str.npos) { return false; } locBuffer++; } return true; }int main() { int m, n; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> list[i]; } for (int i = 0; i < m; i++) { cin >> str; for (int j = 0; j < n; j++) { // 只要一位特征串 if (str.size() == 1) { if (list[j].find(str) != str.npos) ans[j]++; } else { // 多位 if (multiMatch(list[j], str)) ans[j]++; } } }for (int i = 0; i < n; i++) { cout << ans[i] << endl; } }

联系邮箱：curren_wong@163.com
CSDN：https://me.csdn.net/qq_41729780
【算法刷题笔记|牛客网 NC20859 兔子的名字】知乎：https://zhuanlan.zhihu.com/c_1225417532351741952
公众号：复杂网络与机器学习
欢迎关注/转载，有问题欢迎通过邮箱交流。