题意
给你两个长度分别为 \(n,m\) 的字符串 \(s,t\)，其中仅包含小写字母、- 和 *，你需要将 - 替换为任意小写字母，* 替换为任意小写字母构成的字符串（可以为空串），问是否可以使得 \(s'=t'\)。
\(n,m\le 2\times 10^6\)，12s。
思路
首先我们有工具：NTT 优化带通配符的字符串匹配。对于两个不含 * 的字符串 \(s,t\)，我们可以求出 \(s\) 能匹配 \(t\) 中的哪些子串。具体地，构造序列 \(a,b\)，如果 \(s_i\) 是通配符则 \(a_i=0\)，否则 \(a_i\) 表示 \(s_i\) 是第几个字母，\(b_i\) 同理。
那么如果 \(s\) 能匹配 \(t_{i,\dots,i+m-1}\)，当且仅当
\[f_i=\sum_{j=0}^{m-1}(t_{i+j}-s_j)^2t_{i+j}s_j=0 \]把括号拆掉后三次差卷积可以计算。
回到原问题，我们发现 * 比较难处理。
经过手玩，\(s,t\) 同时都有 * 的情况是简单的：令 \(p\) 为最小的数使得 \(s_p\) 或 \(t_p\) 为 *，则 \(s_{0,\dots,p-1}\) 要匹配 \(t_{0,\dots,p-1}\)，后缀同理。而 \(s,t\) 同时不含 * 的情况更为平凡，直接逐位判断即可。
于是经过平凡的操作，我们将问题转化成了 \(s\) 形如 \(*s_1*s_2*\cdots*s_k*\)，而 \(t\) 不含 * 的形式。于是就有贪心：\(s_1\) 匹配 \(t\) 中第一个能匹配的位置，并将其匹配位置及其前所有字符都删去，按同样的方式依次匹配 \(s_{2\dots k}\)，如果全部成功匹配则有解，否则无解。
但如果每次直接将 \(s_i\) 与 \(t\) 做 NTT 字符串匹配复杂度不可接受，我们发现时间复杂度的浪费主要为我们只需要找到 \(s_i\) 在 \(t\) 中第一个匹配的位置，但我们把所有位置是否匹配都求出来了。
如果字符串无通配符，则我们可以在 \(O(1)\) 时间内判断 \(s_i\) 与 \(t\) 中以 \(p\) 开头的等长字符串是否匹配，所以我们可以从左向右依次判断，以 \(O(1)\) 的代价删去一个字符。而带上通配符，我们可以在 \(O((r-l+|s_i|)\log (r-l+|s_i|))\) 的时间复杂度内内判断 \(s_i\) 与 \(t\) 中以 \([l,r]\) 开头的等长字符串是否匹配，据此，我们可以想到优化的思路：在 \(l\) 相关的时间复杂度内删去 \(l\) 个字符。
我们每次把 \(s_i\) 与 \(t\) 的前 \(2|s_i|\) 个字符进行匹配，在 \(p\) 位置匹配成功则把 \(t_{p+|s_i|-1}\) 及以前的字符全部删除，否则删除 \(t\) 的前 \(l\) 个字符。容易发现这符合我们的需求——在 \(O(|s_i|\log |s_i|)\) 的时间复杂度内删去了不少于 \(|s_i|\) 个字符。
时间复杂度 \(O(n\log n)\)。
核心代码：
inline Poly MulR(const Poly &a,const Poly &b){
int n=a.size(),m=b.size();
Poly F=a,G=b;
reverse(G.begin(),G.end());
F=F*G;
Poly H;
for(int i=0;i<n-m+1;i++)
H.push_back(F[i+m-1]);
return H;
}
int n,m;
short s[M],t[M];
Poly F1,G1,F2,G2,F3,G3,H;
inline int check(int l1,int r1,int l2,int r2){
F1.clear(),F2.clear(),F3.clear();
for(int i=l2;i<=r2;i++){
int v=t[i];
F1.push_back(v),F2.push_back(v*v),F3.push_back(v*v*v);
}
G1.clear(),G2.clear(),G3.clear();
for(int i=l1;i<=r1;i++){
int v=s[i];
G1.push_back(v),G2.push_back(v*v),G3.push_back(v*v*v);
}
H=MulR(F3,G1)+MulR(F1,G3)-MulR(F2,G2)*2;
for(int i=0;i<H.size();i++)
if(!H[i])
return l2+i;
return -1;
}
int main(){
// freopen("G.in","r",stdin);
n=read(),m=read();
bool fls=0,flt=0;
for(int i=1;i<=n;i++){
char c=getc();
if(c=='*') fls=1,s[i]=-1;
else s[i]=c=='-'?0:c-'a'+1;
}
for(int i=1;i<=m;i++){
char c=getc();
if(c=='*') flt=1,t[i]=-1;
else t[i]=c=='-'?0:c-'a'+1;
}
if(!fls&&!flt){
bool fl=n==m;
for(int i=1;i<=n;i++)
fl&=!s[i]||!t[i]||s[i]==t[i];
return puts(fl?"Yes":"No"),0;
}
if(fls&&flt){
for(int i=1;;i++)
if(s[i]==-1||t[i]==-1) break;
else if(s[i]&&t[i]&&s[i]!=t[i]) return puts("No"),0;
for(int i=n,j=m;;i--,j--)
if(s[i]==-1||t[j]==-1) break;
else if(s[i]&&t[j]&&s[i]!=t[j]) return puts("No"),0;
return puts("Yes"),0;
}
if(!fls) swap(n,m),swap(s,t);
Prefix(n+m);
int sts=0,stt=0,eds=0,edt=0;
for(int i=1;;i++)
if(s[i]==-1||t[i]==-1){ sts=stt=i;break; }
else if(s[i]&&t[i]&&s[i]!=t[i]) return puts("No"),0;
for(int i=n,j=m;;i--,j--)
if(s[i]==-1||t[j]==-1){ eds=i,edt=j;break; }
else if(s[i]&&t[j]&&s[i]!=t[j]) return puts("No"),0;
while(s[sts]==-1) sts++;
for(int i=sts,j=stt;i<=eds;){
int r=i;
while(r+1<=n&&s[r+1]!=-1) r++;
int l=r-i+1;
while(1){
if(j>edt) return puts("No"),0;
int jr=min(edt,j+l*2);
int tmp=check(i,r,j,jr);
if(tmp==-1) j+=l;
else{ j=tmp+l;break; }
}
while(r+1<=n&&s[r+1]==-1) r++;
i=r+1;
}
puts("Yes");
}