题目链接：
https://nanti.jisuanke.com/t/19970
思路：
KMP做这道题的想法
模板ABCA变成 -1 -1 -1 3
询问CBAABCA变成 -1 -1 -1 1 3 5 3（记作diff)
next数组是 0 1 2 3
匹配CBAABCA的时候，我记f[i]为匹配到第i个字符时候，模板串最长能匹配到哪，模板串匹配的最长位置为j
这样f就是 1 2 3 1 2 3 4
为什么f[4]变成了1，因为匹配到第四个的时候，要求s[4]==s[4-1]，j一直跳到1，这时候diff[4]>=next，意味着这个diff[4]已经没用了，要变成-1
这样diff就变成了 -1 -1 -1 -1 3 5 3，此时j指向1
然后求f[5]，发现5-3>=j，就把3变成-1，来匹配，因为让s[5]==s[2]已经没有用了，模板串长度不够，不需要考虑这个3
这样diff又变成了-1 -1 -1 -1 -1 5 3，此时next匹配上了，变成2
一直下去，求出所有的f
复杂度不会算，因为询问串每次都跳fail，不知道会覆盖多少个不同的状态，最坏情况是可能会是len^2？
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int fail[N],cnt[N],deep[N];
map<int,int>ch[N];
int tot,root;
int newnode(){
tot++;
ch[tot].clear();
fail[tot]=0; cnt[tot]=0;
return tot;
}
void init(){
for (int i=0;i<=tot;i++) ch[i].clear();
root=newnode();
}
void insert(int *s,int n){
int now=root;
int _deep=0;
for (int i=1;i<=n;i++){
_deep++;
int w=s[i];
assert(w<_deep);
if (!ch[now].count(w)) ch[now][w]=newnode();
now=ch[now][w];
deep[now]=_deep;
}
cnt[now]++;
}
int getnext(int u,int w){
if (w>=deep[u]+1) w=-1;
// for (auto &p:ch[u]){
// printf("ch %d:%d %d\n",u,p.first,p.second);
// }
// printf("%d %d %d \n",u,w,ch[u].count(w));
while(u!=root&&!ch[u].count(w)){
u=fail[u];
if (w>=deep[u]+1) w=-1;
}
if (ch[u].count(w)) return ch[u][w];
return u;
}
void build(){
queue<int>Q;
fail[root]=root;
for (auto &p:ch[root]){
int v=p.second;
fail[v]=root;
Q.push(v);
}
while(!Q.empty()){
int u=Q.front(); Q.pop();
for (auto &p:ch[u]){
int v=p.second;
fail[v]=getnext(fail[u],p.first);
Q.push(v);
}
}
}
int T;
int vis[N];
bool query(int *s,int n){
int now=root;
for (int i=1;i<=n;i++){
int w=s[i];
now=getnext(now,w);
for (int v=now;v!=root&&vis[v]!=T;v=fail[v]){
vis[v]=T;
if (cnt[v]) return 1;
}
}
return 0;
}
char s[N*10];
int a[N*10];
int pre[26];
int main(){
int t; scanf("%d",&t);
for (int cas=1;cas<=t;cas++){
init();
int n; scanf("%d",&n);
for (int i=1;i<=n;i++){
memset(pre,0,sizeof(pre));
scanf("%s",s+1);
int m=0;
for (int j=1;s[j];j++){
int w=s[j]-'A';
if (pre[w]) a[j]=j-pre[w];
else a[j]=-1;
pre[w]=j;
m++;
// printf("%d ",a[j]);
}
insert(a,m);
}
build();
// for (int i=1;i<=tot;i++) printf("%d %d %d\n",i,fail[i],deep[i]);
scanf("%d",&n);
printf("Case #%d: ",cas);
for (int i=1;i<=n;i++){
T++;
memset(pre,0,sizeof(pre));
scanf("%s",s+1);
int m=0;
for (int j=1;s[j];j++){
int w=s[j]-'A';
if (pre[w]) a[j]=j-pre[w];
else a[j]=-1;
pre[w]=j;
m++;
}
if (query(a,m)) printf("Y");
else printf("N");
if (i==n) printf("\n");
else printf(" ");
}
}
}
