首先可以对n个目标串单独进行处理。
对于每个目标串，考虑把模式串按'*'进行划分为cnt段。首尾两段一定得于原串进行匹配。剩下的cnt-2段尽量与最靠左的起点进行匹配。
对于剩下的cnt-2段。每段又可以通过‘?’划分为k个子串。对每个子串求出hash值。然后通过枚举起点与目标串的某个区间的hash进行判断。
就可以在O(k)的时间进行每一次的枚举了。对于目标串区间的hash值。可以通过预处理hash前缀进行O(1)询问。
而最多进行len次枚举。所以总复杂度为O(n*len*k).
另外判断子串匹配目标串的区间用AC自动机也是可以的。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi 3.1415926535 # define eps 1e-4 # define MOD 1000000007 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; inline int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=100010; //Code begin... char str[N], ss[N]; int hs[N], shs[N], xing[55], pos, bg, ed; struct Node{int x, len; bool flag;}node[55]; int get_hash(int l, int r){return shs[r]-shs[l-1]*hs[r-l+1];} bool check(int be, int L){ int sum=0; FOR(i,1,L) if (node[i].flag) sum+=node[i].x; else sum+=node[i].len; if (be+sum>ed+1) return false; FOR(i,1,L) { if (node[i].flag) be+=node[i].x; else { if (get_hash(be,be+node[i].len-1)!=node[i].x) return false; be+=node[i].len; } } return true; } bool sol(){ int num, sum, l, cnt, ll; FOR(i,2,pos) { if (xing[i]-xing[i-1]<=1) continue; sum=num=l=ll=cnt=0; FOR(j,xing[i-1]+1,xing[i]-1) { if (str[j]=='?') { ++num; if (l) node[++cnt].x=sum, node[cnt].len=l; node[cnt].flag=0, sum=l=0; } else { sum=sum*MOD+str[j]; ++l; if (num) node[++cnt].x=num, node[cnt].flag=1, num=0; } } if (l) node[++cnt].x=sum, node[cnt].len=l; node[cnt].flag=0, sum=l=0; if (num) node[++cnt].x=num, node[cnt].flag=1, num=0; while (bg<=ed&&!check(bg,cnt)) ++bg; if (!check(bg,cnt)) return false; FOR(i,1,cnt) if (node[i].flag) ll+=node[i].x; else ll+=node[i].len; bg+=ll; } return true; } int main () { hs[0]=1; FO(i,1,N) hs[i]=hs[i-1]*MOD; scanf("%s",str+1); int T; scanf("%d",&T); while (T--) { scanf("%s",ss+1); pos=0; bg=1; ed=strlen(ss+1); for (int i=1; ss[i]; ++i) shs[i]=shs[i-1]*MOD+ss[i]; int l=1, r=strlen(str+1); int flag=0; while (str[l]!='*'&&l<=r&&bg<=ed) { if (str[l]=='?'||str[l]==ss[bg]) ++l, ++bg; else {flag=1; break;} } while (str[r]!='*'&&l<=r&&bg<=ed) { if (str[r]=='?'||str[r]==ss[ed]) --r, --ed; else {flag=1; break;} } if (flag) {puts("NO"); continue;} FOR(i,l,r) if (str[i]=='*') xing[++pos]=i; if (pos==0&&bg<=ed) {puts("NO"); continue;} puts(sol()?"YES":"NO"); } return 0; }