USACO Section 3.1 Contact - AC自动机..

赤果果的AC自动机～并且比较阉割～比完整的AC自动机好写多了..

　首先构造一个完全二叉树..根据题目要求构造１３层..根节点为１，根的左孩子为２，右孩子为３．．依次类推..那么一个节点P的父亲为P/2...左孩子为P*2...右孩子为P*2+1..所以整棵树用一维数组来存就okl了...这棵树转化为字典数..可以看成..１是超级节点..２是'0'...３是'1'..４是'00'..５是'01'..6是'10'..７是'11'..依次类推...

　构造Fail指针很方便～～初值： father[1]=0 , father[2]=father[3]=1 然后一个for循环就可以了...

　AC自动机做好后就边读边做匹配了～～计数器不仅是当前指针的位置++...其所有的father再father等等的也都++...当所到达的层数大于１３时那么指针就不下去就是～～

输出有点恶心...我WA了６次有５次是输出的问题～这个～～～根据题目和数据自己调调吧～～

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: contact
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
#define oo 2000000000
#define ll long long
using namespace std;   
struct node
{
     int w,t;      
}s[20001];
int i,k,p,A,B,N,num,m,father[20001];
char c;
bool cmp(node a,node b)
{ 
     if (a.t!=b.t) return a.t>b.t;
     return a.w<b.w;
}
int main()
{
     freopen("contact.in","r",stdin);  
     freopen("contact.out","w",stdout);   
     for (i=1;i<=20000;i++) 
     {
            s[i].w=i;
            s[i].t=0;    
     }
     father[1]=0; father[2]=father[3]=1;
     for (i=4;i<=20000;i++)
     {
            if (i%2) father[i]=father[i/2]*2+1;
            else father[i]=father[i/2]*2;   
     }
     scanf("%d%d%d\n",&A,&B,&N);
     p=1;
     //2047
     while (~scanf("%c",&c))
     {
            if (c!='1' && c!='0') continue;
            if (c-'0')
            {
                   k=p=p*2+1; 
                   while (k)
                   {
                        s[k].t++; 
                        k=father[k];     
                   }                  
            }else
            {
                   k=p=p*2; 
                   while (k)
                   {
                        s[k].t++; 
                        k=father[k];     
                   }                     
            }
            if (p>4095) p=father[p];
     }
     sort(s+1,s+20000,cmp);
     k=1;
     for (i=1;i<=A;i++) k*=2;
     A=k;
     k=1;
     for (i=1;i<=B+1;i++) k*=2;
     B=k-1;     
     num=0; m=0;
     int out[20],h,g=1;
     for (i=1;i<=20000;i++)
     if (s[i].w>=A && s[i].w<=B)
     {
            if (!s[i].t) break;       
            if (s[i].t!=m)
            {
                   if (num==N) break;
                   if (m && g%6!=0) printf("\n");
                   m=s[i].t; 
                   num++;  g=0;
                   printf("%d\n",m);     
            }
            g++; 
            if (g%6!=1) printf(" "); 
            h=0;
            while (s[i].w!=1)
            {
                  out[++h]=s[i].w%2;
                  s[i].w/=2;      
            }    
            for (i=h;i>=1;i--) printf("%d",out[i]);   
            if (g%6==0) printf("\n");        
     } 
     if (g%6) printf("\n");
     return 0;   
}