简要题意

给你一个模式串 \(s\) 和一些待匹配字符串 \(t_i\)。

模式串 \(s\) 由 \(\texttt{A,C,T,*,?}\) 组成。其中 \(\texttt{A,C,T}\) 表示这个位置匹配这个字符本身。\(\texttt{*}\) 可以匹配任意个字符（包括 \(0\) 个）。\(\texttt{?}\) 可以匹配一个任意字符。

你需要求出有多少个待匹配字符串无法匹配。

\(1\leq N\lt 500,1\leq |s|,|t_i|\leq 10^3\)

思路

原题的 Bug：RNA 中好像没有 Thymine（胸腺嘧啶）（DNA 才有） 。有 Adenine(腺嘌呤，维生素 B4）、Guanine（鸟嘌呤）、Cytosine（胞嘧啶）、Uracil（尿嘧啶）（这个 DNA 没有）。

对于每一个 \(t\)，我们考虑 DP，设 \(f(i,j)\) 为 \(s[1:i]\) 是否与 \(t[1:j]\) 匹配。

则当 \(s_i=\texttt{?}\) 时，可以匹配一个元素，也就是 \(f(i-1,j-1)\)。

当 \(s_i=\texttt{*}\) 时，可以匹配任意个元素，我们分两个情况考虑:

• 匹配 \(0\) 个，即 \(f(i-1,j)\)。
• 匹配多个，即 \(f(i,j-1)\)。（因为可以大于 \(1\) 个，所以 \(i\) 不需要减 \(1\)，直接让 \(\ast\) 发挥它的作用，继续匹配）。

所以 \(f(i,j)=f(i-1,j)\operatorname{Or}f(i,j-1)\)。

其他情况在满足前面都匹配上的情况下直接匹配，\(f(i,j)=f(i-1,j-1)\operatorname{And} [s_i=t_j]\)。

所以状态转移方程就出来了：

最后看看 \(f(|s|,|t|)\) 是否为 \(\operatorname{false}\) 即可。

最后讲一讲边界，首先显然 \(f_{0,0}=\operatorname{true}\)，其次对于所有的 \(s\) 前面的连续的 \(\ast\) 的 \(s_i\)，\(f_{i,0}=\operatorname{true}\)。

时间复杂度 \(O(n|s||t|)\)。

代码

#include <bits/stdc++.h>
#define int long long
#define elif else if
using namespace std;

int n,m;
string s,t;
bool f[505][505];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>s>>n;
    s=" "+s;
    f[0][0]=1;
    for(int i=1;i<s.size()&&s[i]=='*';i++) f[i][0]=1;
    while(n--){
        cin>>t;
        t=" "+t;
        for(int i=1;i<s.size();i++){
            for(int j=1;j<t.size();j++){
                if(s[i]=='?') f[i][j]=f[i-1][j-1];
                elif(s[i]=='*') f[i][j]=f[i-1][j]||f[i][j-1];
                else f[i][j]=f[i-1][j-1]&&(s[i]==t[j]);
            }
        }
        m+=!f[s.size()-1][t.size()-1];
        for(int i=1;i<s.size();i++){
            for(int j=1;j<t.size();j++) f[i][j]=0;
        }
    }
    cout<<m;
    return 0;
}