HDU 6170 Two strings（dp）

http://acm.hdu.edu.cn/showproblem.php?pid=6170

题意：
给出两个字符串，第二个字符串中会有两个特殊字符$.$和$*$，$.$可以匹配任一字符，$*$可以使前面一个字符出现任意次，注意，可以出现0次，也就是把前面那个删了。问这两个串是否可以匹配。

思路：

一开始以为是模拟。。。囧。

$dp[i][j]$表示第二个字符串的前i个和第一个字符串的前j个是否可以匹配。一开始$dp[0][0]=0$。

情况分为以下几种：

如果 $s2[i] == . 或者s2[i] == s1[j]$时，$dp[i][j]$ 的状态取决于状态$dp[i-1][j-1]$。

如果$s2[i] == ‘*‘$时，$dp[i][j] == dp[i-1][j] | dp[i-2][j]$，因为可以让前面的字符出现1次或者0次。并且当$(dp[i-1][j-1] || dp[i][j-1]) $ && $s1[j-1] == s1[j]$ 时，$dp[i][j]$必定为true。可以仔细想一想。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 const int maxn=2500+5;
15 
16 char s1[maxn],s2[maxn];
17 int dp[maxn][maxn];
18 
19 int main()
20 {
21     //freopen("in.txt","r",stdin);
22     int T;
23     scanf("%d",&T);
24     while(T--)
25     {
26         scanf("%s%s",s1+1,s2+1);
27         int len1=strlen(s1+1),len2=strlen(s2+1);
28         memset(dp,0,sizeof(dp));
29         dp[0][0]=1;
30         for(int i=1;i<=len2;i++)
31         {
32             if(i==2 && s2[i]=='*')  dp[i][0]=1;
33             for(int j=1;j<=len1;j++)
34             {
35                 if(s2[i]==s1[j] || s2[i]=='.')  dp[i][j]=dp[i-1][j-1];
36                 else if(s2[i]=='*')
37                 {
38                     dp[i][j]=dp[i-1][j]||dp[i-2][j];
39                     if((dp[i-1][j-1]||dp[i][j-1])&& s1[j-1]==s1[j])  dp[i][j]=1;
40                 }
41             }
42         }
43         if(dp[len2][len1])  puts("yes");
44         else puts("no");
45     }
46     return 0;
47 }