题目链接
原题解：
只有一个模式的时候
考虑现在有模式串$M$和文本串$S$，我们想知道是否有$S$的某个子串符合$M$。
先对模式串和文本串进行转化，变成一个整数序列。对于某个字母，如果是在串中第一次出现，那么对应整数$0$；如果不是，则对应到其上一次出现的距离。
比如串$ABBACAB$对应整数序列$0013024$
将$0$看成有一定限制的通配符。
比如在$ABBACAB(0013024)$中查找模式$ABC(000)$.
现在我们可以定义两个整数序列同构的条件。
我们称$M=S$当且仅当对于所有的$i$，以下两条至少有一条满足。
1.$M_i=S_i$
2.$(S_i>ivee S_i=0) wedge (M_i>i vee M_i=0)$
这个$=$具有很重要的传递性。
利用这个全新的相等关系去做KMP就好了，为了利用这个相等关系，你需要知道比较的两个字符串的长度。
多个模式
类似KMP算法，我们可以对整数序列$S$计算$fail$函数。
多个模式的时候利用AC自动机即可。
为了利用那个相等关系，我们需要知道AC自动机上每个节点所对应的串的长度，即对应节点的深度。
补充：
我用暴力过了。字符串题用随机数据就离谱……
代码（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> #define IL inline #define RG register #define _1 first #define _2 second using namespace std; typedef unsigned int UI; #define RI RG int #define RC RG char #define RU RG UI #define RB RG bool const int N=1e5; const int M=5e5; const int S=26; IL bool va(RC ch){ return 'A'<=ch&&ch<='Z'; } int n,m; int k,v1[S+3],v2[S+3]; vector<int>s[N+3],t[M+3]; int main(){ scanf("%d ",&n); for(RI i=1;i<=n;i++){ k=0; memset(v1,0,sizeof v1); for(RC ch=getchar();va(ch);ch=getchar()){ if(!v1[ch-'A']) v1[ch-'A']=++k; s[i].push_back(v1[ch-'A']); } } scanf("%d ",&m); for(RI i=1;i<=m;i++) for(RC ch=getchar();va(ch);ch=getchar()) t[i].push_back(ch-'A'); for(RI i=1;i<=m;i++){ RB flag=false; for(RI j=1;j<=n&&!flag;j++) for(RU k=0;k+s[j].size()<=t[i].size()&&!flag;k++){ memset(v1,0,sizeof v1); memset(v2,0,sizeof v2); RB yes=true; for(RU p=0;p<s[j].size()&&yes;p++){ if(!v1[s[j][p]]&&!v2[t[i][k+p]]){ v1[s[j][p]]=t[i][k+p]; v2[t[i][k+p]]=s[j][p]; } else if(v1[s[j][p]]&&!v2[t[i][k+p]]) if(v1[s[j][p]]==t[i][k+p]) v2[t[i][k+p]]=s[j][p]; else yes=false; else if(!v1[s[j][p]]&&v2[t[i][k+p]]) if(s[j][p]==v2[t[i][k+p]]) v1[s[j][p]]=t[i][k+p]; else yes=false; else if(v1[s[j][p]]!=t[i][k+p] ||s[j][p]!=v2[t[i][k+p]]) yes=false; } flag=yes; } printf("%s ",flag?"Yes":"No"); } return 0; }