字典树模板

/*  2011-09-30
    自己的hash函数模板
    zoj3013 hash映射：            T = 200
    zoj3013 字典树：              T = 80
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min( a, b ) ((a)<(b)?(a):(b))

/* Hash define */
#define wordsize 10
#define nodesize 12501
#define hashsize 100000

typedef struct node
{
    char  word[ wordsize ];
    node* next;
}list;
list  dict[ nodesize+1 ];
list* head[ hashsize+1 ];

class Hash
{
    private:
        static int mul[ 8 ];
        int size;
    public:
        Hash(){size = 0;memset( head, 0, sizeof( head ) );}
        int hash( char* word, int l ) {
            int value = 0;
            for ( int i = 0 ; i < l ; ++ i )
                value = (value+word[ i ]*mul[ i ])%hashsize;
            return value;
        }
        void insert( char* word, int l ) {
            int id = hash( word, l );
            for ( int i = 0 ; i < l ; ++ i )
                dict[ size ].word[ i ] = word[ i ];
            dict[ size ].word[ l ] = ‘\0‘;
            dict[ size ].next = head[ id ];
            head[ id ] = &(dict[ size ++ ]);
        }
        bool find( char* word, int l ) {
            int i,id = hash( word, l );
            for ( list* p = head[ id ] ; p ; p = p->next ) {
                for ( i = 0 ; i < l ; ++ i )
                    if ( word[ i ] != p->word[ i ] ) break;
                if ( i == l ) return true;
            }return false;
        }
};
int Hash::mul[ 8 ] = {31,131,313,1313,3131,13131,31313,131313};
/* Hash end */

char word[ 12500 ][ 10 ];
char pass[ 100 ][ 4105 ];
int  last[ 4105 ];
int  shor[ 4105 ];

void output( int s, char* p, int L )
{
    if ( s < 0 ) return;
    output( last[ s ], p, L );
    for ( int i = last[ s ]+1 ; i <= s ; ++ i )
        printf("%c",p[ i ]);
    if ( s < L ) printf("#");
    else printf("\n");
}  

int main()
{
    int m,n;
    while ( scanf("%d%d",&m,&n) != EOF ) {
        for ( int i = 0 ; i < m ; ++ i )
            scanf("%s",word[ i ]);
        for ( int i = 0 ; i < n ; ++ i )
            scanf("%s",pass[ i ]);
        
        Hash trie;
        for ( int i = 0 ; i < m ; ++ i )
            trie.insert( word[ i ], strlen( word[ i ] ) );

        for ( int i = 0 ; i < n ; ++ i ) {
            int L = strlen( pass[ i ] );
            for ( int j = 0 ; j < L ; ++ j ) {
                last[ j ] = -1;
                shor[ j ] = L+1;
            }shor[ 0 ] = 1;
            for ( int j = 0 ; j < L ; ++ j ) {
                for ( int l = 1 ; l <= 8 ; ++ l )
                    if ( trie.find( &pass[ i ][ j ], min( l, L-j ) ) ) {
                        int tail = j+min( l, L-j )-1;
                        if ( j && shor[ tail ] <= shor[ j-1 ] ) continue;
                        if ( !j && shor[ tail ] > shor[ j-1 ] ) shor[ tail ] = 0;
                        else shor[ tail ] = shor[ j-1 ];
                        last[ tail ] = j-1;
                    }
                if ( j > 0 && shor[ j ] > shor[ j-1 ]+1 ) {
                    shor[ j ] = shor[ j-1 ]+1;    
                    last[ j ] = j-1;
                }
            }

            printf("%d\n",shor[ L-1 ]);
            output( L-1, pass[ i ], L-1 );
        }
    }
    return 0;
}

字典树模板,布布扣,bubuko.com

字典树模板

原文：http://blog.csdn.net/mobius_strip/article/details/21910053