ACM模版

描述

题解

这个 dp 很好，好多人都尝试用正则过关，但是不知道有没有大佬如愿以偿…… WA 了两发，找到了两个 bug ，一个是因为 ∗ 可以表示前一个字符出现 0 次；另一个是因为当开头存在星号时，其实是第二个字符为星号时，我们需要考虑这个第一个的字符出现 0 次，也就是考虑类似于 a 和 n∗a 的情况。

这个题花费了一段时间，但是不得不说，这个题出得很有水平。尽管我讨厌他(ノω<。)ノ))☆.。讨厌

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define clr(a, b) memset(a, b, sizeof(a))

using namespace std;

const int MAXN = 2555;

char str1[MAXN];
char str2[MAXN];
int dp[MAXN][MAXN];

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        clr(dp, 0);
        str1[0] = str2[0] = str1[1] = str2[1] = '#';

        scanf("%s%s", str1 + 2, str2 + 2);
        int n = (int)strlen(str1 + 1);
        int m = (int)strlen(str2 + 1);

        dp[0][0] = dp[1][1] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (str2[j] == '.')
                {
                    dp[i][j] |= dp[i - 1][j - 1] | dp[i][j - 1];
                }
                else
                {
                    if (str2[j] == '*')
                    {
                        dp[i][j] |= dp[i][j - 1] | dp[i][j - 2];
                        if (str1[i - 1] == str1[i])
                        {
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                    else
                    {
                        if (str1[i] == str2[j])
                        {
                            dp[i][j] |= dp[i - 1][j - 1];
                        }
                        else
                        {
                            dp[i][j] = 0;
                        }
                    }
                }
            }
        }

        if (dp[n][m])
        {
            puts("yes");
        }
        else
        {
            puts("no");
        }
    }

    return 0;
}