stdKonjac's Blog

An AC a day keeps the WA away ~

【Isfind】

【问题描述】

给出一个长度为n的字符串S,给出m组询问,每次询问给出一个非空字符串,判断这个字符串是否是S的子序列,如果是,那么输出“Y”,否则输出”N”

【输入格式】

第一行两个数n,m,分别表示字符串长度以及询问数。

下一行一个长度为n的字符串S。

接下来m行,每行一个询问的非空字符串。

【输出格式】

输出共m行,每行一个大写字母“Y”或者“N”。

【输入样例】

4 3

acbc

abc

cba

cc

【输出样例】

Y

N

Y

【数据范围】

对于100%的数据 n,m≤10^6,询问字符串的总长度不超过4×10^6

每次询问的字符串长度不超过n,所有字符串中仅包含小写字母。

其实是个暴力加点小优化都能过的题……

数据太水,直接YY了一个伪Trie树就过了

对于一个字符串a……b……b 匹配了a之后肯定是跳到第一个b去更好。

所以记录一下每个位置的字母的与它距离最近且在它之后的其它字母在哪里 每次匹配的时候跳就是了。

毕竟 数据水嘛……

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.