坏掉的数字键｜字符串匹配

第三题 - A23468.坏掉的数字键

题目链接跳转：A23468.坏掉的数字键

根据题意，我们需要统计在 $N$ 个字符串中，有多少个字符串不包括字符 $D$。循环遍历一个一个匹配实在太麻烦了，直接使用 string 类自带的 .find() 函数即可。直接用 Cpp 的内置函数即可（内置函数大法真好用）。

a.find(b) 表示在 a 中寻找 b。如果找到了就返回 b 第一次在 a 中出现的位置，否则就返回 string::npos。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "Hello, world!";
    
    // 查找字符 'w'。
    size_t found = str.find('w');
    // 如果 found == string::npos 则代表没找到，否则返回的第一个匹配的索引。
    if (found != string::npos) cout << "'w' found at: " << found << endl;
    else cout << "'w' not found" << endl;
    return 0;
}

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int T, n, total;
string d, tmp;

int main(){
    cin >> T;
    while(T--){
        cin >> n >> d;
        total = 0;
        for (int i=1; i<=n; i++){
            cin >> tmp;
            // 如果找不到，就说明这个字符串可以被题目中的“键盘”给打出来。
            if (tmp.find(d) == string::npos)  
                total++;
        }
        cout << total << endl;
    }
    return 0;
}

本题的 Python 代码如下：

T = int(input())

while T:
	T -= 1
	n, d = input().split()
	arr = input().split()
	ans: int = 0
	for i in arr:
		ans += 1 if i.find(d) == -1 else 0
	print(ans)

本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间复杂度约为 $O(n \times d)$，其中 d 表示读入进的字符串长度。更进一步地，a.find(b) 函数的时间复杂度为 $O(\text{lena} \times \text{lenb})$。其中，lena 与 lenb 分别代表两个字符串的长度。对于本道题而言，lenb 的值永远为 $1$。