using namespace std; typedef unsigned long long ull; #define maxnode 500010 #define sigma_size 26 #define maxn 100010 #define X 997 struct { int x,y; Point(int x=0,int y=0):x(x),y(y) {} }po[maxn]; struct Trie { int ch[maxnode][sigma_size]; int val[maxnode]; int id[maxnode]; int sz; void init() { sz=1; memset(id,-1,sizeof(id)); memset(ch[0],0,sizeof(ch[0])); val[0]=0; } int idx(char c) { return c-'a'; } void insert(char *s,int n,int o) { int u=0; for(int i=0; i<n; i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; val[u]++; } id[u]=o; } void getPoint(int u,int r,bool ty){ if(~id[u]){ r++; if(!ty) po[id[u]].x=r; else po[id[u]].y=r; } for(int i=0; i<26; i++) { if(ch[u][i]){ getPoint(ch[u][i],r,ty); r+=val[ch[u][i]]; } } } Point findSeg(char *s){ int n=strlen(s),u=0; int r=0; for(int i=0; i<n; i++) { int c=idx(s[i]); if(!ch[u][c]) return Point(); for(int j=0;j<c;j++) if(ch[u][j]) r+=val[ch[u][j]]; if(~id[u]) r++; u=ch[u][c]; } return Point(r+1,r+val[u]); } }pref,suff; char p[maxn],s[maxn]; int ans[maxn]; struct Line{ int x,y1,y2,ty,id; Line() {} Line(int x,int y1,int y2,int ty,int id):x(x),y1(y1),y2(y2),ty(ty),id(id) {} bool operator <(const Line &rhs)const{ return x<rhs.x||x==rhs.x&&y2<rhs.y2; } }L[maxn*3]; struct SegTree{ int sumv[maxn*4]; void init(){ memset(sumv,0,sizeof(sumv)); } void update(int o,int L,int R,int p){ if(L==R) sumv[o]++; else{ int M=(L+R)/2; if(p<=M) update(o*2,L,M,p); else update(o*2+1,M+1,R,p); sumv[o]++; } } int query(int o,int L,int R,int qL,int qR){ if(qL<=L&&R<=qR) return sumv[o]; int M=(L+R)/2,ans=0; if(qL<=M) ans+=query(o*2,L,M,qL,qR); if(qR>M) ans+=query(o*2+1,M+1,R,qL,qR); return ans; } }T; set<ull> st; ull xp[maxn]; int main() { int ca; xp[0]=1; for(int i=1;i<maxn;i++) xp[i]=xp[i-1]*X; scanf("%d",&ca); while(ca--) { int n,q; memset(ans,0,sizeof(ans)); st.clear(); scanf("%d%d",&n,&q); pref.init();suff.init(); for(int i=0; i<n; i++) { scanf("%s",s); int len=strlen(s); ull h=0; for(int j=0;j<len;j++){ h=h*X+s[j]-'0'; } st.insert(h); pref.insert(s,len,i); reverse(s,s+len); suff.insert(s,len,i); } pref.getPoint(0,0,0); suff.getPoint(0,0,1); for(int i=0;i<n;i++) L[i]=Line(po[i].x,po[i].y,0,0,0); Point e; int k=n,px,py,sx,sy; for(int te=0;te<q;te++){ scanf("%s%s",p,s); e=pref.findSeg(p); if(e.x==0) continue; px=e.x;py=e.y; int l2=strlen(s); reverse(s,s+l2); e=suff.findSeg(s); if(e.x==0) continue; int l1=strlen(p); ull h,h1=0,h2=0; reverse(s,s+l2); for(int j=0;j<l1;j++) h1=h1*X+p[j]-'0'; for(int j=0;j<l2;j++) h2=h2*X+s[j]-'0'; for(int i=0;i<min(l1,l2);i++){ if(p[l1-i-1]!=s[i]) break; h1-=(s[i]-'0')*xp[i]; h=h1*xp[l2-i-1]+h2; if(st.count(h)) ans[te]--; } sx=e.x;sy=e.y; L[k++]=Line(px-1,sx,sy,-1,te); L[k++]=Line(py,sx,sy,1,te); } sort(L,L+k); T.init(); for(int i=0;i<k;i++){ if(!L[i].y2) T.update(1,1,n,L[i].y1); else ans[L[i].id]+=L[i].ty*T.query(1,1,n,L[i].y1,L[i].y2); } for(int i=0;i<q;i++) printf("%dn",ans[i]); } return 0; }
|
近期评论