牛客網 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

公衆号：複雜網絡與機器學習

歡迎關注/轉載，有問題歡迎通過郵箱交流。