BZOJ-1212: [HNOI2004]L语言（TRIE+DP

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

trie上的DP，不知道AC自动机怎么弄这题。。。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define maxn 1001000

#define check( ch ) ( ch >= 'a' && ch <= 'z' )

#define maxv 310

 

struct node {

    int child[ 26 ] ;

    bool flag ;

    node(  ) {

        flag = false ;

        memset( child , 0 , sizeof( child ) ) ;

    }

} T[ maxv ] ;

 

int n , m , V = 0 ;

 

int s[ maxn ] , len ;

 

void getstr(  ) {

    len = 0 ; int ch ;

    for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

    s[ ++ len ] = ch - 'a' ;

    for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) s[ ++ len ] = ch - 'a' ;

}

 

int f[ 2 ][ maxv ] , k ;

 

int Dp(  ) {

    memset( f[ 0 ] , 0 , sizeof( f[ 0 ] ) ) , k = 0 ;

    int ans = 0 ;

    f[ 0 ][ 0 ] = 1 ;

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

        bool flag = true ;

        memset( f[ k ^ 1 ] , 0 , sizeof( f[ k ^ 1 ] ) ) ;

        for ( int j = 0 ; j <= V ; ++ j ) if ( f[ k ][ j ] ) {

            if ( T[ j ].child[ s[ i ] ] ) {

                flag = false ;

                f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] = max( f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] , f[ k ][ j ] + 1 ) ;

                if ( T[ T[ j ].child[ s[ i ] ] ].flag ) {

                    ans = max( ans , f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] - 1 ) ;

                    f[ k ^ 1 ][ 0 ] = max( f[ k ^ 1 ][ 0 ] , f[ k ^ 1 ][ T[ j ].child[ s[ i ] ] ] ) ;

                }

            }

        }

        k ^= 1 ;

        if ( flag ) break ;

    }

    return ans ;

}

 

int main(  ) {

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

    while ( n -- ) {

        getstr(  ) ;

        int t = 0 ;

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

            if ( ! T[ t ].child[ s[ i ] ] ) T[ t ].child[ s[ i ] ] = ++ V ;

            t = T[ t ].child[ s[ i ] ] ;

        }

        T[ t ].flag = true ;

    }

    while ( m -- ) {

        getstr(  ) ;

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

    }

    return 0 ;

}