BZOJ-3172: [Tjoi2013]单词（AC自动机解法）

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

之前这道题用SA水过了，刚学AC自动机，就先拿这道题当例题练练手吧。。。

论IO优化的重要性

4e4a20a4462309f746e3fc66700e0cf3d7cad632.jpg.png

上面那个未加优化，下面那个加了优化。。。

代码（第一次写，虽然有点丑。。。）：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ; 
 
#define MAXL 2000010
#define MAXN 210
#define MAXV 1000010
 
struct node {
        node *child[ 26 ] , *fail ;
        int cnt ;
        node (  ) {
               cnt = 0 ; memset( child , 0 ,sizeof( child ) ) ; fail = NULL ;
        }
} *roof = new( node ) , *q[ MAXV ] , *w[ MAXN ] ;
 
int getstr( char *s ) {
        int len = 0 , ch ;
        for ( ch = getchar(  ) ; ! ( ch >= 'a' && ch <= 'z' ) ; ch = getchar(  ) ) ;
        s[ len ++ ] = ch ;
        for ( ch = getchar(  ) ; ch >= 'a' && ch <= 'z' ; 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' );
}
 
char s[ MAXL ] ;
int n ;
 
int main(  ) {
        getint( n ) ;
        for ( int i = 0 ; i ++ < n ; ) {
               int len = getstr( s ) ;
               node *t = roof ;
               for ( int j = 0 ; j < len ; j ++ ) {
                       if ( ! t -> child[ s[ j ] - 'a' ] ) t -> child[ s[ j ] - 'a' ] = new( node ) ;
                       t = t -> child[ s[ j ] - 'a' ] ; t -> cnt ++ ;
               }
               w[ i ] = t ;
        }
        int head = 0 , tail = 0 ;
        for ( int i = 0 ; i < 26 ; i ++ ) if ( roof -> child[ i ] ) {
               q[ ++ tail ] = roof -> child[ i ] ; q[ tail ] -> fail = roof ;
        }
        while ( head < tail ) {
               node *v = q[ ++ head ] ;
               for ( int i = 0; i < 26; i ++ ) if ( v -> child[ i ] ) {
                       node *u = v -> fail ; q[ ++ tail ] = v -> child[ i ] ;
                       for ( ; u != roof && ! u -> child[ i ] ; u = u -> fail ) ;
                       q[ tail ] -> fail = u -> child[ i ] ? u -> child[ i ] : roof ;
               }
        }
        for ( int i = tail ; i ; i -- ) q[ i ] -> fail -> cnt += q[ i ] -> cnt ;
        for ( int i = 0 ; i++ < n ; ) putint( w[ i ] -> cnt ) ;
        return 0 ;
}