1212: [HNOI2004]L语言

题解：

　　看完题目之后就觉得可以暴力在字典树上之间询问，一开始还傻了以为用文章来建，肯定用单词啊：

　　那么我们可以用一个v数组表示当前字符串1~i的区间能够被覆盖，v[0]就初始化一下

　　然后一开始就把位置挪到当前已经处理到的能覆盖的位置x，然后从x+1开始在字典树上跑，跑到一个单词的结尾就更新当前位置的v（即使单词有包含关系也没所谓，只要路过就会更新，找不到了才结束，那肯定跑到最后一个位置最优啊），然后重复操作（换一个单词）

　　严重吐槽：说好的是字典，哪来的同样的单词？？？于是没有听企鹅的话...结果就WA了，膜一发捞niang发现他一开始和我一样傻...吐槽吐槽吐槽！！！

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 struct node

 {

     int c[],s;

     node()

     {

         memset(c,-,sizeof(c));

         s=;

     }

 }tr[];int cnt;

 void bt(char *s,int root)

 {

     int x=root,len=strlen(s+);

     for(int i=;i<=len;i++)

     {

         int y=s[i]-'a'+;

         if(tr[x].c[y]==-)tr[x].c[y]=++cnt;

         x=tr[x].c[y];

     }

     tr[x].s++;//有同样的单词...所以要++ ORZ

 }

 int n,m;

 char s[],st[];

 int v[];

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     {

         scanf("%s",s+);

         bt(s,);

     }

     for(int i=;i<=m;i++)

     {

         scanf("%s",st+);int len=strlen(st+);

         v[]=i;int x=,ans=;

         while(x<=len)

         {

             while(v[x]!=i)

             {

                 x++;

                 if(x==len+)break;

             }

             int r=;

             for(int k=x+;k<=len;k++)

             {

                 int y=st[k]-'a'+;

                 if(tr[r].c[y]==-)break;

                 else

                 {

                     r=tr[r].c[y];

                     if(tr[r].s>)v[k]=i;

                 }

             }

             x++;

         }

         for(int j=len;j>=;j--)if(v[j]==i){ans=j;break;}

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

bzoj1212: [HNOI2004]L语言（字典树）

1212: [HNOI2004]L语言

最新文章

热门文章