Skip to content

牛客网 NC20859 兔子的名字#

目录#

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#

对于 的数据

对于 的数据

|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;
    }
}

联系邮箱：curren_wong@163.com

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

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

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

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

二维码

Back to top