404

# 题目

Giving two strings and you should judge if they are matched.
The first string contains lowercase letters and uppercase letters.
The second string contains lowercase letters, uppercase letters, and special symbols: “.” and “*”.
. can match any letter, and  means the front character can appear any times. For example, “a.b” can match “acb” or “abb”, “a” can match “a”, “aa” and even empty string. ( “*” will not appear in the front of the string, and there will not be two consecutive “*”.

The first line contains an integer T implying the number of test cases. (T≤15)
For each test case, there are two lines implying the two strings (The length of the two strings is less than 2500).

For each test case, print “yes” if the two strings are matched, otherwise print “no”.

3
aa
a*
abb
a.*
abb
aab

yes
yes
no

# 题解

## 正则表达式

.* 在标准的正则表达式中是匹配任意字符串,而这里是匹配任意的连续字符串

## 动态规划

• 串内容相同(或者存在'.'或者为第一个位置):
dp[i][j] |= dp[i-1][j-1]
• 匹配到*:
dp[i][j] |= dp[i][j-2] | dp[i][j-1]
• 匹配到*,并且当前位置和其左面的字符相同:
dp[i][j] |= dp[i-1][j]

bbbbbb匹配a*b*

# 代码

## 正则表达式

#include <cstdio>
#include <iostream>
#include <regex>
using namespace std;

void string_replace(string &s1, const string &s2, const string &s3) {
string::size_type pos = 0;
string::size_type a = s2.size();
string::size_type b = s3.size();
while ((pos = s1.find(s2, pos)) != string::npos) {
s1.replace(pos, a, s3);
pos += b;
}
}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);
int T;
cin >> T;

while (T--) {
string text, re;

cin >> text >> re;
//cout << text << endl << re << endl;
string_replace(re, ".*", "(.)?\\1*");
// cout << text <<" "<< re << endl;

regex e(re);
cout << (regex_match(text, e) ? "yes" : "no") << endl;
}

return 0;
}

## 动态规划

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 3505;

char a[maxn], b[maxn];
bool dp[maxn][maxn];

int main() {
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;

// scanf("%d", &T);
// getchar();
while (T--) {
cin >> a >> b;
// scanf("\n%[^\n]\n%[^\n]", a, b);
// fgets(a,maxn,stdin);
// fgets(b,maxn,stdin);

memset(dp, false, sizeof(dp));

// printf("%d\na:%s\nb:%s\n",T, a, b);
int n = strlen(a);
int m = strlen(b);

for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
// 第一个位置
if ((a[i] == b[j] || b[j] == '.') && i == 0 && j == 0)
dp[i][j] |= true;
// 从左上角转移过来
if ((a[i] == b[j] || b[j] == '.') && i > 0 && j > 0)
dp[i][j] |= dp[i - 1][j - 1];
// 特判
if ((a[i] == b[j] || b[j] == '.') && b[1] == '*' && i == 0)
dp[i][j] = true;
// * 匹配
// 从上面的上面转移过来（匹配0个）
//从上面转移过来（匹配1个）
if (b[j] == '*')
dp[i][j] |= (j >= 2 ? dp[i][j - 2] : 0) |
(j >= 1 ? dp[i][j - 1] : 0);
// 从左面转移过来（*往后续）
if (b[j] == '*' && i >= 1 && a[i - 1] == a[i])
dp[i][j] |= dp[i - 1][j];
}

// for (int i = 0; i < n; ++i) {
//     for (int j = 0; j < m; ++j)
//         printf("%d ", dp[i][j]);
//     printf("\n");
// }
// printf("%s\n", (dp[n - 1][m - 1] ? "yes" : "no"));
cout << (dp[n - 1][m - 1] ? "yes" : "no") << endl;
}
return 0;
}

• 点击查看/关闭被识别为广告的评论