rt,目前已确认不是模数问题。
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
const int mod=469762049,G=3;
int fpow(int a,int b){
b=(b%(mod-1)+mod-1)%(mod-1);
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
vector<int>rev;
void reverse(int len,vector<int>&f){
rev.resize(len);
rev[0]=0;
for(int i=0;i<len;i++){
rev[i]=rev[i>>1]>>1;
if(i&1)rev[i]|=(len>>1);
if(rev[i]>i)swap(f[i],f[rev[i]]);
}
}
void NTT(vector<int>&f,int len,int op){
reverse(len,f);
for(int l=2;l<=len;l<<=1){
int wn=fpow(G,op*(mod-1)/l);
for(int j=0;j<len;j+=l){
int w=1;
for(int i=j;i<j+l/2;i++){
int g=f[i],h=w*f[i+l/2]%mod;
f[i]=(g+h)%mod;
f[i+l/2]=(g-h+mod)%mod;
w=w*wn%mod;
}
}
}
if(op==-1){
int inv=fpow(len,mod-2);
for(int i=0;i<len;i++)f[i]=f[i]*inv%mod;
}
}
int n,m;
char s[2000005],t[2000005];
deque<int>a,b;
int val[30];
void Sol(vector<int>&A,deque<int>&S){
if(A.empty())return;
int l=A.size();
reverse(A.begin(),A.end());
// cerr<<"_+"<<l<<endl;
while(S.size()>=l){
vector<int>B,C=A;
for(int i=0;i<min((int)S.size(),l+l-1);i++)B.push_back(S[i]);
int ll=B.size(),len=1;
while(len<l+ll)len<<=1;
if(len>5e6)exit(1);
vector<int>X(len),Y(len),Z(len);
while(B.size()<len)B.push_back(0);
while(C.size()<len)C.push_back(0);
for(int i=0;i<len;i++)X[i]=B[i],Y[i]=C[i]*C[i]%mod*C[i]%mod;
NTT(X,len,1);
NTT(Y,len,1);
for(int i=0;i<len;i++)Z[i]=(Z[i]+X[i]*Y[i]%mod)%mod;
for(int i=0;i<len;i++)X[i]=B[i]*B[i]%mod,Y[i]=C[i]*C[i]%mod;
NTT(X,len,1);
NTT(Y,len,1);
for(int i=0;i<len;i++)Z[i]=(Z[i]-2*X[i]%mod*Y[i]%mod+mod)%mod;
for(int i=0;i<len;i++)X[i]=B[i]*B[i]%mod*B[i]%mod,Y[i]=C[i];
NTT(X,len,1);
NTT(Y,len,1);
for(int i=0;i<len;i++)Z[i]=(Z[i]+X[i]*Y[i]%mod)%mod;
NTT(Z,len,-1);
for(int i=l-1;i<l+l-1;i++){
if(Z[i]==0){
for(int j=0;j<i+1;j++)S.pop_front();
return;
}
}
for(int i=0;i<l;i++)S.pop_front();
}
puts("No");
exit(0);
}
mt19937_64 Rand(time(0));
signed main()
{
for(int i=1;i<=26;i++)val[i]=Rand()%mod;
scanf("%lld%lld%s%s",&n,&m,s+1,t+1);
for(int i=1;i<=n;i++){
if(s[i]=='-')a.push_back(0);
else if(s[i]=='*')a.push_back(-1);
else a.push_back(val[s[i]-'a'+1]);
}
for(int i=1;i<=m;i++){
if(t[i]=='-')b.push_back(0);
else if(t[i]=='*')b.push_back(-1);
else b.push_back(val[t[i]-'a'+1]);
}
while(!a.empty()&&!b.empty()&&a.front()!=-1&&b.front()!=-1){
int x=a.front(),y=b.front();
a.pop_front();
b.pop_front();
if(x*y%mod*(x-y)%mod!=0){
puts("No");
return 0;
}
}
while(!a.empty()&&!b.empty()&&a.back()!=-1&&b.back()!=-1){
int x=a.back(),y=b.back();
a.pop_back();
b.pop_back();
if(x*y%mod*(x-y)%mod!=0){
puts("No");
return 0;
}
}
if(a.empty()||b.empty()){
if(a.empty()&&b.empty())puts("Yes");
else{
if(a.empty())swap(a,b);
bool f=1;
for(int x:a)f&=(x==-1);
if(f)puts("Yes");
else puts("No");
}
return 0;
}
int s0=0,s1=0;
for(int x:a)s0+=(x==-1);
for(int x:b)s1+=(x==-1);
if(s0&&s1){
puts("Yes");
return 0;
}
if(s1)swap(a,b);
vector<int>las;
// for(int x:a)cerr<<x<<' ';cerr<<endl;
// for(int x:b)cerr<<x<<' ';cerr<<endl;
for(int i=1;i<a.size();i++){
if(a[i]==-1){
Sol(las,b);
las.clear();
// for(int x:b)cerr<<x<<" ";
// cerr<<endl;
}
else las.push_back(a[i]);
}
puts("Yes");
return 0;
}