hdu 6170
2024-10-02 08:00:26
dp:
http://blog.csdn.net/qq_28954601/article/details/77484676
#include <bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = ;
bool dp[maxn][maxn];
char s[maxn];
char t[maxn];
int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
scanf("%s",s+);
scanf("%s",t+);
s[]=t[]='';
int len1=strlen(s)-;
int len2=strlen(t)-;
mt(dp,false);
dp[][]=true;
for(int i=;i<=len2;++i){
if(i==&&t[i]=='*') dp[i][]=true;
for(int j=;j<=len1;++j){
if(t[i]==s[j]||t[i]=='.'){
dp[i][j]=dp[i-][j-]; //如果正常匹配的话,dpij就是从dpi-1j-1转移过来的
}else if(t[i]=='*'){
dp[i][j]=dp[i-][j]|dp[i-][j];//如果这个*号的前面一个或者前面的第二个可以匹配到j位置的,则可以,我觉得是使用在多个*的时候的
if((dp[i-][j-]||dp[i][j-])&&s[j-]==s[j]) //如果是sj-1==sj的话,可以自己举例子看看就会清楚这是什么情况了
dp[i][j] = true;
}
}
}
puts(dp[len2][len1]?"yes":"no");
}
return ;
}
最新文章
- photoshopcc基础教程
- 【python3】collections系列介绍
- 计算机学院大学生程序设计竞赛(2015’12)The Country List
- 配置navigation bar外观
- Round Numbers (排列组合)
- (转)dedecms代码详解 很全面
- Windows上帝模式
- To the end
- macOS的OpenCL高性能计算
- jQuery遍历—each()方法遍历对象和数组
- 论Activity的转换
- final关键字。
- c#反射(1)
- C# WebApi过滤器(开发接口必备利器)
- 【JS】JS格式化文件大小 单位:Bytes、KB、MB、GB
- Highcharts属性与Y轴数据值刻度显示Y轴最小最大值
- win7 64位系统彻底卸载mysql
- Ubuntu 录制视频并制作成gif图
- java.lang.UnsupportedClassVersionError: com/my/test/TestUser : Unsupported major.minor version 52.0
- Mysql监控调优