BZOJ-2434: [Noi2011]阿狸的打字机（AC自动机

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2434

明显先建立AC自动机，然后对于y上的每一个点，沿着fail走，能走到x的就答案+1，这个暴力思路很明显，但是明显过不了。

每个节点只有一个fail，那么就把fail作为其父亲节点建fail树，那么，答案就是x的子树中存在的y的节点个数，这个就用DFS序+BIT维护就可以了。

代码：

有没有IO优化再次对比明显了，C++读入个字符串就真的那么慢么。。。（最下面的未加优化）

a044ad345982b2b7759bc4b033adcbef76099bba.jpg.png

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

 

using namespace std ;

 

#define MAXN 100100

#define lowbit( x )((- x )& x )

#define clear( x )memset( x ,0,sizeof( x ))

#define MAXV 500100

 

int getstr(char*s ){

    int len =0, ch ;

    for( ch =getchar(  );!(( ch >='a'&& ch <='z')|| ch =='B'|| ch =='P'); ch =getchar(  ));

    s[ len ++]= ch ;

    for( ch =getchar(  );( ch >='a'&& ch <='z')|| ch =='B'|| ch =='P'; ch =getchar(  )) s[ len ++]= ch ;

    return len ;

}

 

void getint(int&t ){

    int ch ;

    for( ch =getchar(  );!( ch >='0'&& ch <='9'); ch =getchar(  ));

    t = ch -'0';

    for( ch =getchar(  ); ch >='0'&& ch <='9'; ch =getchar(  )) t *=10, t += ch -'0';

}

   

void putint(int t ){

    if(! t )putchar('0')

    ;else{

        int ans[20];

        ans[0]=0;

        for(; t ; t /=10) ans[++ ans[0]]= t %10;

        for(int i = ans[0]; i ; i --)putchar('0'+ ans[ i ]);

    }

    putchar('\n');

}

 

struct node{

        int fail , father , child[26];

        node (  ){

               fail = father =0;clear( child );

        }

} v[ MAXV ];

 

char s[ MAXN ];

int V =0, cnt =0, w[ MAXN ];

 

void Make_trie(  ){

        int len =getstr( s );

        int t =0;

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

               if( s[ i ]=='P'){

                       w[++ cnt ]= t ;

               }else if( s[ i ]=='B'){

                       t = v[ t ].father ;

               }else{

                       if(! v[ t ].child[ s[ i ]-'a']) v[ t ].child[ s[ i ]-'a']=++ V ;

                       v[ v[ t ].child[ s[ i ]-'a']].father = t ;

                       t = v[ t ].child[ s[ i ]-'a'];

               }

        }

}

 

queue<int>Q ;

 

void Make_fail(  ){

        while(! Q.empty(  )) Q.pop(  );

        for(int i =0; i <26; i ++)if( v[0].child[ i ]){

               Q.push( v[0].child[ i ]);

        }

        while(! Q.empty(  )){

               int ve = Q.front(  ); Q.pop(  );

               for(int i =0; i <26; i ++)if( v[ ve ].child[ i ]){

                       Q.push( v[ ve ].child[ i ]);int u = v[ ve ].fail ;

                       for(; u &&! v[ u ].child[ i ]; u = v[ u ].fail );

                       v[ v[ ve ].child[ i ]].fail = v[ u ].child[ i ]? v[ u ].child[ i ]:0;

               }

        }

}

 

struct edge{

        edge *next ;

        int t ;

        edge (  ){

               next = NULL ;

        }

}*head[ MAXV ];

 

void AddEdge(int s ,int t ){

        edge *p =new( edge );

        p -> t = t , p -> next = head[ s ];

        head[ s ]= p ;

}

 

int arr[ MAXV *2], in[ MAXV ], out[ MAXV ], Index =0;

 

void dfs(int t ){

        arr[ in[ t ]=++ Index ]= t ;

        for( edge *p = head[ t ]; p ; p = p -> next )dfs( p -> t );

        arr[ out[ t ]=++ Index ]= t ;

}

 

void Fail_tree(  ){

        clear( head );

        for(int i =0; i ++< V ;)AddEdge( v[ i ].fail , i );

        dfs(0);

}

 

struct qtype{

        qtype *next ;

        int x , r ;

}*fro[ MAXV ];

 

void Insert(int s ,int t ,int r ){

        qtype *p =new( qtype );

        p -> x = s , p -> r = r , p -> next = fro[ t ];

        fro[ t ]= p ;

}

 

int m ;

 

void Init_query(  ){

        getint( m );clear( fro );

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

               int s , t ;

               getint( s ),getint( t );Insert( w[ s ], w[ t ], i );

        }

}

 

struct Bit{

        int a[ MAXV *2], N ;

       

        void Init(int _N ){

               N = _N ;clear( a );

        }

       

        void Add(int x ,int y ){

               for(int i = x ; i <= N ; i +=lowbit( i )) a[ i ]+= y ;

        }

       

        int Sum(int l ,int r ){

               int rec =0;

               for(int i = r ; i ; i -=lowbit( i )) rec += a[ i ];

               for(int i = l -1; i ; i -=lowbit( i )) rec -= a[ i ];

               return rec ;

        }

} bit ;

 

int ans[ MAXN ];

 

void Dfs(int t ){

        bit.Add( in[ t ],1);

        for( qtype *p = fro[ t ]; p ; p = p -> next )

            ans[ p -> r ]= bit.Sum( in[ p -> x ], out[ p -> x ]);

        for(int i =0; i <26; i ++)if( v[ t ].child[ i ]){

               Dfs( v[ t ].child[ i ]);

        }

        bit.Add( out[ t ],-1);

}

 

void Solve(  ){

        bit.Init( Index );

        Dfs(0);

}

 

int main(  ){

        Make_trie(  );

        Make_fail(  );

        Fail_tree(  );

        Init_query(  );

        Solve(  );

        for(int i =0; i ++< m ;)putint( ans[ i ]);

        return 0;

}