题目

{% fold 点击显/隐题目 %}

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
{% endfold %}

题解

正则表达式

基本上可以在读题都一半的时候确定是正则表达式的问题
通常来说,这种问题一半会使用AC自动机来解答,不过其实可以试一下C++11的正则表达式库的

首先确定题意的时候可以发现,这里和标准的正则表达式语句存在一些不同
.* 在标准的正则表达式中是匹配任意字符串,而这里是匹配任意的连续字符串
相当于 (.)?\1*

当然,还需要考虑*可以匹配0次,但是这是正则表达式本身就有的语法
因此,简单思路就是先把 .* 替换成 (.)?\1* (在源码里要写成(.)?\\1*)
然后直接匹配即可
相应部分的代码如下
具体实现代码见正则表达式源码

需要特别注意的是,虽然同样是无脑用库,但是Java会超时
另外C++11的Regex库存在的bug比较多,只有比较简单的匹配才能放心使用
比如aba匹配abababa是无法得到3的,无法使用类似这样的(?=(aba))零宽断言语法来实现(其他语言可以)

动态规划

按照动态规划的思路,很容易得到dp[i][j]表示字符串a的前i个字符和字符串b的前j的字符能否匹配
假如我们要匹配 aaaaaa 和 ab*a*

对于第一个位置(最左上角),显然当两者相等的时候为true
其同一行已经没有能够匹配的了
第二行可以发现b不等于a全部都是false
第三行的*可以将上一行的b匹配0次,这时,当前位置能否匹配成功取决于它上面的上面是否能匹配
第四行有a和a相同,位置能否匹配取决于其左上角的能否匹配
第五行的*可以匹配任意长度,匹配两个时候相当于该位置取决于上面能否匹配;匹配更多个的时候相当于只要其对应的a中的字符和它左面的相同,就可以将左面能否匹配的状态传递过来

另外,.可以看作一个普通字符,只是能和所有的字符都匹配
综上所述,总共只包含很少的状态转移条件

  • 串内容相同(或者存在'.'或者为第一个位置):
    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]

这样就可以写出基本的dp框架了
然后就会发现我们漏掉了一个特殊情况
bbbbbb匹配a*b*
由于开始位置匹配失败,导致后面所有位置都无法为true
只有b[1]=='*'的时候才会导致这个错误
相当于特殊情况下的状态转移1
其条件如下: 串内容相同或者存在.,同时i=0,b[1]='*'

这样就可以写出完整的状态转移方程了

代码

正则表达式

{% fold 点击显/隐代码 %}```cpp Two strings https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
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;

}

{% endfold %}

## 动态规划
{% fold 点击显/隐代码 %}```cpp Two strings https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#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;
}

{% endfold %}