涉及知识点：字符串匹配 题意：给出母串 s，给出 m 次询问，每次询问给出的子串 si 是否是 s 的子序列 思路：如果直接考虑双重for循环比较会超时，看着是道字典树的题，但是没写过字典树，就写了个递推思路的代码，设 nex[ i ][ j ] 表示第 i 个位置的字母后第一个 j + 'a'
展开全文
Solution 直观的想法是直接扫描两个字符串进行比较。这样的复杂度是 的。 然后可以发现子序列中字母的相对位置是不变的，所以可以维护一个数组 ， 表示第 个位置之后最近的字母 所在的位置。这个数组可以 处理： ，然后在倒序循环一遍即可预处理出 数组。 对于每个要判断的字符串 ，建
展开全文
思路：m次询问看字符串是不是给定字符串的子序列暴力的做法就是直接两个循环去匹配 复杂度m * strlen(a) * Σ(strlen(b)) 这复杂度显然是不可接受的那么考虑一下预处理cnt[i][j] 表示当前位置为i下一个字符为j的位置 倒着遍历字符串即可预处理一遍之后，每次循环跑的次数就
展开全文
题意 给定字符串 ，有 个询问，每个询问给出一个字符串 , 问 是否是 的子序列。 分析 先记录每个字母在 中出现的位置。对于字符串 的每个 ，我们肯定尽可能在 中往前取。假设上一次取的是 。那么这一次就要在所有 出现的位置中找到第一个比 大的。这个可以二分解决。 代码如下 #inc
展开全文
Description 月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让
展开全文
题目分析：序列自动机板子题。注意字符串字符均为小写字母，因此我们设一个T数组，T[i][j]表示在i位置右边，离i最近的j+‘a’字母的下标，我们可以从后到前求出T数组。在询问时，需要对每个字符串判断，我们可以利用T数组在主串上进行跳跃匹配。若该字符串利用T数组能匹配到尾部，输出YES，否则输出NO
展开全文
一维数组不好储存先后位置 所以用二维数组nt[i][j]记录当前位置i后面最靠近字母j的位置后缀一下，从后往前记录 特例由于 nt[i][a[i]-'a']=i; 记录的是它本身的位置所以后面查找成功后位置加一 d=nt[d][b[j]-'a']+1;否则遇到相同连续字符会一直在该位置上逗留 #i
展开全文
考虑子序列自动机，每个地方自动跳转到下一个字符的位置，进行跳转~
然后模拟这一个过程就好啦！
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
char ch[N];
int ne[N][30];
int ma
展开全文
Solution ##Code #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N =
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
