当前位置：首页 > news >正文

pyyzDay11

news 2025/10/14 11:08:35

落课了

模拟赛

T1

大炮

dp[i][j]表示第一个串1_{i和第二个串1}j的位置能否匹配

扫一遍判断即可

注意前缀*的情况特判，以及初始化

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{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-48;ch=getchar();}return x*f;
}
map<char,bool> mm;
int dp[5005][5005],maxx[5005];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);string S,t;cin>>S>>t;string s="";int N=S.size();int m=t.size();for(int i=0;i<m;i++){mm[t[i]]=1;}for(int j=0;j<N;j++){if(S[j]=='*'||S[j]=='?') continue;if(!mm[S[j]]){cout<<"NO"<<'\n';return 0;}}int fl=0;for(int i=0;i<N;i++){if(!fl&&S[i]!='*'){fl=1;s+=S[i];}else if(fl){s+=S[i];}}int n=s.size();if(fl){for(int j=0;j<m;j++){if(s[0]==t[j]||s[0]=='?') dp[0][j]++;} }else{if(s[0]==t[0]||s[0]=='?') dp[0][0]++;else{cout<<"NO"<<'\n';return 0;}}for(int i=1;i<n;i++){for(int j=0;j<m;j++){if(s[i]>='a'&&s[i]<='z'){if(s[i]==t[j]&&dp[i-1][j-1]>0) dp[i][j]++;}else if(s[i]=='?'){if(dp[i-1][j-1]>0) dp[i][j]++;}else{if(dp[i-1][j-1]){dp[i][j]++;dp[i+1][j]++;}if(maxx[i-1]) dp[i][j]++;}maxx[i]=max(maxx[i],dp[i][j]);}}if(dp[n-1][m-1]>0) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';return 0;
}