这道题我写了个01DP,f[i][j]表示跑到Trie上第i个节点，匹配到字符串第j位行不行

　　然后重点在*号无限匹配怎么处理

　　经过一番脑洞我们可以发现*号无限匹配可以拆成两种情况：

　　1：匹配数无条件+1，但是字符串仍然匹配到底j位

　　2：直接跳过去了qwq

　　对应设计状态转移方程就好了

　　然后这个算法……我卡时卡空间勉强过

　　卡时不知道怎么办……也许能循环展开什么的？

　　卡空间的话，可以设滚动数组。

　　f[i][j]中的i不再代表Trie上第i个节点，而是代表深度第i层的节点

　　DP的时候用dfs的方法DP，DP完了统计一下就可以把原来叶子占用的空间清掉腾给别人

　　Orz rqy，这真是个神办法

　　

// luogu-judger-enable-o2#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 505#define maxl 1020using namespace std;int tree[maxn*maxn][10],tot;int fail[maxn*maxn];char s[maxl];char c[maxl];int pnt[maxn];bool f[200000][maxn];inline int count(char i){ if(i=='A') return 0; if(i=='T') return 1; if(i=='C') return 2; if(i=='G') return 3; if(i=='*') return 4; return 5;}void update(int x){ int n=strlen(c+1),now=0; for(int i=1;i<=n;++i){ if(tree[now][count(c[i])]==0) tree[now][count(c[i])]=++tot; now=tree[now][count(c[i])]; } pnt[x]=now; return;}void makefail(){ queue
           
            q; for(int i=0;i<6;++i) if(tree[0][i]) q.push(tree[0][i]); while(!q.empty()){ int from=q.front(); q.pop(); for(int i=0;i<6;++i){ int &now=tree[from][i]; if(now==0){ now=tree[fail[from]][i]; continue; } fail[now]=tree[fail[from]][i]; q.push(now); } } return;}int main(){ scanf("%s",s+1);int len=strlen(s+1); int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s",c+1); update(i); } //makefail(); f[0][0]=1; for(int i=0;i<=tot;++i){ for(register int j=0;j