湖南小企业网站建设怎么做,wordpress 备案号,施工企业安全生产评价表下载,邢台123贴吧牛客网链接 时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 月月和华华一起去吃饭了。期间华华有事出去了一会儿#xff0c;没有带手机。月月出于人类最单纯的好奇心#…牛客网链接 时间限制C/C 2秒其他语言4秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 题目描述 月月和华华一起去吃饭了。期间华华有事出去了一会儿没有带手机。月月出于人类最单纯的好奇心打开了华华的手机。哇她看到了一片的QQ推荐好友似乎华华还没有浏览过。月月顿时醋意大发出于对好朋友的关心为了避免华华浪费太多时间和其他网友聊天她要删掉一些推荐好友。但是为了不让华华发现产生猜疑破坏了他们的友情月月决定只删华华有可能搭讪的推荐好友。 月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪当且仅当小姐姐的昵称是他的昵称的子序列。为了方便华华和小姐姐的昵称只由小写字母构成。为了更加方便保证小姐姐的昵称长度不会比华华的长。 现在月月要快速的判断出哪些推荐好友要删掉因为华华快回来了时间紧迫月月有点手忙脚乱所以你赶紧写个程序帮帮她吧 输入描述: 第一行输入一个字符串A表示华华的昵称。 第二行输入一个正整数N表示华华的推荐好友的个数。 接下来N行每行输入一个字符串BiB_iBi表示某个推荐好友的昵称。 输出描述: 输出N行对于第i个推荐好友如果华华可能向她搭讪输出Yes否则输出No。 注意大写同时也要注意输出效率对算法效率的影响。 示例1 输入
noiauwfaurainairtqltqlmomomo
8
rain
air
tql
ntt
xiaobai
oiiiooo
orzcnzcnznb
ooooo输出
Yes
Yes
Yes
Yes
No
Yes
No
No备注: 题解 字符串问题 有两个解决方法字典树和序列自动机都能做我想到的 这里就不讲字典树了 序列自动机 序列自动机就是用一个数组next[i][j]来记录数组a第i位的字符j在i后第一次出现的坐标。 设串长为n,字符集大小为a预处理时间复杂度为O(n*a) 序列自动机讲解
for(int in;i;i--)
{for(int j1;ja;j) next[i-1][j]next[i][j];next[i-1][s[i]]i;
}代码:
#includeiostream
#includecstdio
#includestring
#includecstring
#includealgorithm
#define forr(n) for(int i1;in;i)
#define fore(n) for(int j1;jn;j)
using namespace std;
const int ma1000004;
char a[ma];
int len;
int w0;
int m;
bool f1;
int next[ma][30];
int main()
{cin(a1);int lenstrlen(a1);for(int ilen;i1;i--){for(int j0;j25;j) next[i-1][j]next[i][j];next[i-1][a[i]-a]i;}cinm;char chgetchar();forr(m){cin(a1);lenstrlen(a1);w0;f1;fore(len){wnext[w][a[j]-a];if(w0){f0;coutN0endl;break;}}if(f!0)coutYesendl;}return 0;
}
