题意:有两个字符串,第一个由大写字母和小写字母组成,第二个由大写字母、小写字母、'.'、‘*’组成。'.'可以代替任意一个字符,‘*’与其前面的字母可以组成多个(eg:a*可以代表a,aa,aaa,……或者是空串)。问两个字符串能否匹配。
分析:dp[i][j]---字符串1长度为i,字符串2长度为j时能否匹配。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define lowbit(x) (x & (-x)) const double eps = 1e-8; inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1; } typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const int MAXN = 2500 + 10; const int MAXT = 10000 + 10; using namespace std; char s1[MAXN], s2[MAXN]; int dp[MAXN][MAXN]; int main(){ int T; scanf("%d", &T); while(T--){ memset(dp, 0, sizeof dp); scanf("%s%s", s1 + 1, s2 + 1); int len1 = strlen(s1); int len2 = strlen(s2); s1[0] = s2[0] = '-'; dp[0][0] = true; dp[0][1] = false; dp[1][0] = false; for(int i = 1; i <= len1; ++i){ for(int j = 1; j <= len2; ++j){ if(dp[i - 1][j] && s2[j] == '*' && s1[i] == s1[i - 1]){ dp[i][j] = true; } if(dp[i][j - 1] && s2[j] == '*'){ dp[i][j] = true; } if(dp[i - 1][j - 1] && (s1[i] == s2[j] || s2[j] == '.' || (s2[j] == '*' && s1[i] == s1[i - 1]))){ dp[i][j] = true; } if(j >= 2 && dp[i][j - 2] && s2[j] == '*'){ dp[i][j] = true; } } } printf("%s ", dp[len1][len2] ? "yes" : "no"); } return 0; }