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 ;
}

最新文章

  1. photoshopcc基础教程
  2. 【python3】collections系列介绍
  3. 计算机学院大学生程序设计竞赛(2015’12)The Country List
  4. 配置navigation bar外观
  5. Round Numbers (排列组合)
  6. (转)dedecms代码详解 很全面
  7. Windows上帝模式
  8. To the end
  9. macOS的OpenCL高性能计算
  10. jQuery遍历—each()方法遍历对象和数组
  11. 论Activity的转换
  12. final关键字。
  13. c#反射(1)
  14. C# WebApi过滤器(开发接口必备利器)
  15. 【JS】JS格式化文件大小 单位:Bytes、KB、MB、GB
  16. Highcharts属性与Y轴数据值刻度显示Y轴最小最大值
  17. win7 64位系统彻底卸载mysql
  18. Ubuntu 录制视频并制作成gif图
  19. java.lang.UnsupportedClassVersionError: com/my/test/TestUser : Unsupported major.minor version 52.0
  20. Mysql监控调优

热门文章

  1. webpack的理解
  2. python调用java--JPype
  3. vuex 闲置状态重置方案
  4. 题解 P3372 【【模板】线段树1 】
  5. [Recompose] Compose Streams of React Props with Recompose’s compose and RxJS
  6. MongoDB 基本使用
  7. mysql python中的pymysql模块使用
  8. ajax --- Ajax跨域请求保证同一个session的问题
  9. 安装配置FreeBSD9全过程体验
  10. Android 设置屏幕不待机