首先通过hash建树

设f[i][j]表示第i个特殊符号从P的第j位开始匹配能到达哪里

记忆化搜索，对于底层贪心匹配。

 

#include
     
      #include
      
       using std::strlen;const int N=510,M=2010;char a[10],tmp[10],b[N][10],s[M];int T,n,m,i,j,k,h[N],son[N][2],len[N],f[N][M];inline int hash(char a[]){  int t=0,j=strlen(a);  for(int i=0;i<5;i++)t=t*27+(i
       
        ='a'&&b[i][0]<='z')son[i][0]=0,len[i]=strlen(b[i]);      else son[i][0]=hash(b[i]),scanf("%s",tmp),scanf("%s",tmp),son[i][1]=hash(tmp);    }    for(i=1;i<=n;i++)if(son[i][0])for(j=0;j<2;j++)for(k=1;k<=n;k++)if(son[i][j]==h[k]){son[i][j]=k;break;}    scanf("%s%s",a,s),m=strlen(s);    for(i=1;i<=n;i++)for(j=0;j<=m;j++)f[i][j]=-1;    for(i=hash(a),k=1;k<=n;k++)if(i==h[k]){j=k;break;}  }  return 0;}