HDU 6170Two strings

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 2510;
 7 char str[N], str1[N];
 8 bool dp[N][N];
 9 int main() {
10     int t;
11     scanf("%d", &t);
12     while(t--) {
13         memset(dp, false, sizeof(dp));
14         scanf("%s %s",str+1, str1+1);
15         int len = strlen(str+1), len1 = strlen(str1+1);
16         dp[0][0] = true;
17         for(int i = 1; i <= len1; i ++) {
18             if(i == 2 && str1[i] == ‘*‘) dp[i][0] = true;
19             for(int j = 1; j <= len; j ++) {
20                 if(str1[i] == ‘.‘ || str1[i] == str[j])
21                     dp[i][j] = dp[i-1][j-1];
22                 else if(str1[i] == ‘*‘) {
23                     dp[i][j] = dp[i-2][j] | dp[i-1][j];
24                     if((dp[i-1][j-1] || dp[i][j-1]) && str[j-1] == str[j])
25                         dp[i][j] = true;
26                 }
27             }
28         }
29         printf("%s\n",dp[len1][len]?"yes":"no");
30     }
31     return 0;
32 }