【NC23053】月月查华华的手机

本文主要是介绍【NC23053】月月查华华的手机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

月月查华华的手机

子序列判断，双指针

思路

将题目翻译一下：

给你一个字符串 $s$，然后给定 $m$ 个字符串的询问，每次询问判断给定的字符串 $t$ 是否是 $s$ 的子序列。

判断子序列的话，按理来说应该比判断子串更简单（在不使用库函数的情况下），因为判断子串需要用到 KMP 算法来优化才能过。那么判断子序列为什么简单呢？

因为判断子序列可以用时间复杂度为 $O(n+m)$ 的天然算法解决，而子串不行（子串的天然算法是 $O(nm)$ 的暴力算法。

那判断子序列的天然算法是什么？

双指针，这里给出伪代码，还是很容易理解的：

// 假设主串是 s, 子串是 t
slen = s.length
tlen = t.length
i = 0, j = 0
while i < slen && j < tlen:while i < slen && s[i] != t[j]:i = i + 1if i == slen:// 找完了也没找到，不是子序列report t is not s's subsequenceelse:j = j + 1i = i + 1 // 思考一下为什么 i 也要加1

代码

#include <stdio.h>#define N 1000005/*** @brief 求字符串 name 是否是 s 的子序列** @param s 主串* @param name 子串* @return int 返回 0 代表不是，否则代表是*/
int is_subseq(const char* s, const char* name) {int i = 0, j = 0;while (s[i] && name[j]) {while (s[i] && s[i] != name[j]) i++;if (!s[i]) return 0;j++;i++;}return !name[j];
}int main(void) {// 华华的昵称char s[N];// 推荐好友个数int n;// 每个好友的昵称char name[N];scanf("%s%d", s, &n);while (n--) {scanf("%s", name);printf("%s\n", is_subseq(s, name) ? "Yes" : "No");}return 0;
}

其他

简单地做一下复杂度的分析，由于有 $m$ 组询问，所以时间复杂度一定要乘以一个 $m$，每次询问花费的时间复杂度为两个字符串的长度 $O(n+k)$，所以最终的时间复杂度为 $O(m(n+k))$，可以近似地看作是 $O(mn)$ 的。

也有预处理的算法，即先预处理主串的字符成一个表，$m$ 次询问就只需要查表即可，不过该算法也需要 $O(mk)$ 的时间复杂度，与本文记录的算法相比优化不是很大，这里不做记录。

当然还有其他更高级（复杂）的算法。

这篇关于【NC23053】月月查华华的手机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---