Skip to content

1350: Cstring Implement II

题目

题目描述

这是一道头文件题目。你要实现给定的两个函数，并把头文件提交到OJ上。在头文件中不允许使用任何标准库。

本题的下发文件可以从 SJTU JBOX 下载。src.hpp为你需要实现的头文件；main.cpp为评测所用的主程序。

在本题中，你需要实现 strcspn 和 strstr 两个函数，它们的定义如下。

C++ /** * @brief "Complementary SPaN"：返回s中第一个未出现在字符串reject中的字符的下标。 * @param s 源字符串 * @param reject 一个字符串，包含不允许出现的字符 * @return 如果存在s中的字符，且其未出现在reject串中，返回第一个这样的字符的下标；否则返回s的长度。 */ size_t strcspn (const char *s, const char *reject);

C++ /** * @brief 查找字符串needle在haystack中第一次出现的位置 * @param haystack 目标字符串 * @param src 源字符串 * @return 返回第一次出现的位置，如果未出现返回空指针 * @par 时间复杂度O(N * M) 即可，其中N、M分别为haystack和needle的长度。 * glibc的实现采用了Knuth-Morris-Pratt算法，这是一个O(N + M) 的字符串匹配算法。它的实现见 <https://github.com/jeremie-koenig/glibc/blob/master-beware-rebase/sysdeps/x86_64/multiarch/strstr.c>。 */ const char *strstr (const char *haystack, const char *needle); // char *strstr (char *haystack, const char *needle); // 不需实现

思考题的答案 不安全。C风格字符串（或指向它的字符指针）的最大缺点就是：按指针传递参数无法携带它底层数组的信息。如果传入超过数组长度的信息，就会引发未定义行为。同样，`gets(s)` 和 `cin >> s` 也会导致类似的问题。 C++采取了一些措施来避免这个问题。比如说，`cin.get` 和 `cin.getline` 必须传入一个参数表示最多输入的字符数——这往往就是数组的大小。为了写出稳健的程序，我们建议使用这两个较为安全的函数。

输入格式

第一行输入 $n$，表示操作数

接下来 $n$ 行，每行一个操作。操作有以下两种：

  • 1 s1 s2 表示需要做 strcspn(s1, s2);
  • 2 s1 s2 表示需要做 strstr(s1, s2);

输出格式

评测程序会输出函数的返回值，每行一个。

  • 如果是 strcspn(s1, s2);，输出它的返回值
  • 如果是 strstr(s1, s2);，输出它的返回值；如果返回nullptr，输出"NOT FOUND"

样例输入

text 4 1 abcdef abcdg 1 abcdef abcdefg 2 abcdefg cde 2 abcdefg cdf

样例输出

text 4 6 cdefg NOT FOUND

数据范围

保证输入的字符串总长度小于等于 $10^6$；strstr保证 $\sum \mathrm{len}(s1) \cdot \mathrm{len}(s2) \le 10^6$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！