用 trie 搜索一下就好了.
- code:
- #include <bits/stdc++.h>
- #define N 10008
- #define setIO(s) freopen(s".in","r",stdin)
- using namespace std;
- char S[24];
- int trie[N*20][27],visx[N],p[N*20],vis[N*20],wo,tot,vistot,n,m,L;
- void ins()
- {
- int u=0,len=strlen(S),i,j;
- for(i=0;i<len;++i)
- {
- int c=S[i]-'a';
- if(!trie[u][c]) trie[u][c]=++tot;
- u=trie[u][c];
- }
- p[u]=1;
- }
- void sol(int x,int l,int f)
- {
- if(l==L&&p[x]&&!f) { wo=1; return; }
- if(l==L&&p[x]&&f)
- {
- if(!vis[x]) vis[visx[++vistot]=x]=1;
- return;
- }
- int c=S[l]-'a';
- if(!f)
- {
- if(l<L) sol(x,l+1,1);
- int i,j;
- for(i=0;i<26;++i)
- {
- if(trie[x][i])
- {
- sol(trie[x][i],l,1);
- if(i!=c) sol(trie[x][i],l+1,1);
- }
- }
- }
- if(l>=L) return;
- if(trie[x][c]) sol(trie[x][c],l+1,f);
- }
- int main()
- {
- // setIO("input");
- scanf("%d%d",&n,&m);
- int i,j;
- for(i=1;i<=n;++i) scanf("%s",S),ins();
- for(i=1;i<=m;++i)
- {
- scanf("%s",S);
- L=strlen(S);
- sol(0,0,0);
- if(wo) printf("-1\n");
- else printf("%d\n",vistot);
- while(vistot) vis[visx[vistot--]]=0;
- wo=0;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3415879.html