Match

考虑询问串 T=a*b 能匹配哪些 S ，把所有 Si 插到一个 Trie 里，如果节点 u 是 Si 的一个祖先且 S=str(u)R 就在 map[hash[ R ]] 里加入 dfsorder[u] ，由于a应该是u的祖先那么u在a的子树里，在map[hash[B]] 里查 [dfsL[a], dfsR[a]] 里有多少点就好。

#include<bits/stdc++.h>
using namespace std;
int xxyy,n,m;
string s,sf[1000000],se[1000000];
struct node
{
 int x,y;
 node ()
 {
  x=y=0;
 }
 void add(char s)
 {
     x=(x*3137+s-'a'+1)%1000000007;
     y=(y*53+s-'a'+1)%1610612741;
 }
} xy[1000000];
bool operator <(const node &xx,const node &yy)
{
 return (xx.x!=yy.x)?xx.x<yy.x:xx.y<yy.y;
}
struct struc
{
 struc *st[30];
 int xx,yy;
 vector <node> sz;
 struc ()
 {
     memset(st,0,sizeof(st));
 }
};
struc *rt;
set <node> sett;
map <node,vector <int> > ma;
void dg(struc *&x,const char *c,node *h)
{
 if (x==NULL) x=new struc();
 x->sz.push_back(*h);
 if (!*c) return;
 dg(x->st[*c-'a'],c+1,h+1);
 return;
}
void dfs(struc *x)
{
 if (x==NULL) return;
 x->xx=++xxyy;
 for (auto xy:x->sz)
  if (sett.count(xy)) ma[xy].push_back(x->xx);
 for (int i=0; i<=25; i++) dfs(x->st[i]);
 x->yy=++xxyy;
 return;
}
int xuv(struc *&x,const char *c,node &h)
{
 if (x==NULL) return 0;
 if (!*c) return upper_bound(ma[h].begin(),ma[h].end(),x->yy)-lower_bound(ma[h].begin(),ma[h].end(),x->xx);
 return xuv(x->st[*c-'a'],c+1,h);
}
void build(string s)
{
 reverse(s.begin(),s.end());
 xy[0]=node();
 for (int i=0; i<s.size(); i++)
 {
  xy[i+1]=xy[i];
  xy[i+1].add(s[i]);
 }
 reverse(xy,xy+s.size()+1);
}
signed main ()
{
 scanf("%d%d",&n,&m);
 for (int i=0; i<n; i++)
 {
  cin>>s;
  build(s);
  dg(rt,s.c_str(),xy);
 }
 for (int i=0; i<m; i++)
 {
  cin>>s;
  sf[i]=s.substr(0,s.find("*"));
  se[i]=s.substr(s.find("*")+1);
  reverse(se[i].begin(),se[i].end());
  node no;
  for (auto xy:se[i]) no.add(xy);
  sett.insert(no);
 }
 dfs(rt);
 for (int i=0; i<m; i++)
 {
  node no;
  for (auto xy:se[i]) no.add(xy);
  printf("%d\n",xuv(rt,sf[i].c_str(),no));
 }
 return 0;
}