Skip to content

1350: Cstring Implement II

题目

题目描述

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

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

在本题中,你需要实现 strcspnstrstr 两个函数,它们的定义如下。

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!