牛客网 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 <iostream>
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;
    }
}
           

联系邮箱：[email protected]

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。