PKU 1816 Wild Words

http://poj.org/problem?id=1816
n個の簡易的な正規表現が与えられる。
マッチングしたいm個の文字列それぞれについて、どの正規表現が完全マッチングしたかを判定しろというような問題。

全探索っぽいものしか思い浮かばなかったので、「正規表現　実装」あたりでググッてみたのですが、即効性のある解決方法が出現しなかったので全探索しました。
TLEしたので入出力をstdioのものにしたり、いろいろと高速化して何とか通りました。

char in[30];
char mat[100000][7];
int len[100000];
int mi;
int msz,isz;

bool dfs(int ipos,int mpos){
  if(ipos==isz && mpos==msz)return true;
  
  if(mat[mi][mpos]=='*'){
    return (mpos<msz&&dfs(ipos,mpos+1)) ||
      (ipos<isz&&mpos<msz&&dfs(ipos+1,mpos+1)) ||
      (ipos<isz&&dfs(ipos+1,mpos));
  }else if(mat[mi][mpos]=='?'){
    return ipos<isz&&mpos<msz&&dfs(ipos+1,mpos+1);
  }else{
    return ipos<isz&&mpos<msz&&
      in[ipos]==mat[mi][mpos] && dfs(ipos+1,mpos+1);
  }
}

main(){
  int n,m;
  scanf("%d%d",&n,&m);
  rep(i,n){
    scanf("%s",mat[i]);
    len[i]=strlen(mat[i]);
  }
  
  while(m--){
    scanf("%s",in);
    isz=strlen(in);
    vector<int>ans;
    rep(i,n){
      mi=i;
      msz=len[i];
      if(dfs(0,0))ans.pb(i);
    }
    if(ans.empty())puts("Not match");
    else{
      printf("%d",ans[0]);
      for(int i=1;i<SZ(ans);i++)printf(" %d",ans[i]);
      putchar('\n');
    }
  }
}