[HNOI2004]L语言

 1 #include<bits/stdc++.h>
 2 #define ll int
 3 #define max(x,y) ((x)>(y)?(x):(y))
 4 #define min(x,y) ((x)<(y)?(x):(y))
 5 #define fur(i,x,y) for(i=x;i<=y;i++)
 6 #define fdr(i,x,y) for(i=x;i>=y;i--)
 7 #define Fur(i,x,y) for(ll i=x;i<=y;i++)
 8 #define Fdr(i,x,y) for(ll i=x;i>=y;i--)
 9 #define in2(x,y) in(x);in(y)
10 #define in3(x,y,z) in2(x,y);in(z)
11 #define in4(a,b,c,d) in2(a,b);in2(c,d)
12 #define clr(x,y) memset(x,y,sizeof(x))
13 #define cpy(x,y) memcpy(x,y,sizeof(x))
14 #define fl(i,x) for(ll i=head[x],to;to=e[i].to,i;i=e[i].next)
15 #define inf 233333333
16 using namespace std;
17 /*---------------------------------------*/
18 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
19 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
20 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
21 namespace fib{char b[300000]= {},*f=b;}inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>‘9‘||c<‘0‘)if(c==‘-‘)f=!f;x=c-48;while((c=gc)<=‘9‘&&c>=‘0‘)x=x*10+c-48;if(f)x=-x;}namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}struct foce{~foce(){pob;fflush(stdout);}} _foce;namespace ib{char b[100];}inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc(‘-‘);x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}inline void outn(ll x){out(x);pc(‘\n‘);}
22 inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
23 inline ll jdz(ll x){return x>=0?x:-x;}
24 /*------------------------------------------------------------------------------------------------*/
25 an
26 #define N 400 
27 ll n,m,sz=1;
28 ll c[N][27];
29 char ch[1000011];
30 bool end[N],vis[1000011];
31 inline ll g(char o){return o-‘a‘;}
32 inline void ins(char *s){
33     ll x=1,len=strlen(s),v;
34     Fur(i,0,len-1){
35         v=g(ch[i]);
36         if(!c[x][v])c[x][v]=++sz;
37         x=c[x][v];
38     }end[x]=1;
39 }
40 inline void dfs(ll x,ll pos){
41     ll v=g(ch[pos]);
42     if(end[x]&&!vis[pos-1])vis[pos-1]=1,dfs(1,pos);
　　　　//&&!vis[pos-1]：剪枝
　　　　//如果是单词结尾，可以跳到根节点匹配
43     if(c[x][v])x=c[x][v],dfs(x,pos+1);//如果有下一个字母，继续搜索
44 }
45 int main(){
46     in2(n,m);
47     Fur(i,1,n)scanf("%s",ch),ins(ch);
48     Fur(i,1,m){
49         scanf("%s",ch);
50         clr(vis,0);dfs(1,0);
51         ll x=strlen(ch)-1;while(x>=0){if(vis[x]){outn(x+1);break;}x--;}
52         if(x==-1)outn(0);
53     }
54 }