Poj Solution 1816

http://poj.org/problem?id=1816

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


char w[100000][7];
int len[100000];
int code[100000];

bool check( char *p, int n, char *w, int m ) {
    bool ans[7][21] = { false };
    char *a = p-1, *b = w-1;

    ans[0][0] = true;

    for( int i=1; i<=n; i++ ) {
        if( a[i] == '?' ) {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ans[i-1][j-1];
        }
        else if( a[i] == '*' ) {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ans[i-1][j] | ans[i][j-1] | ans[i-1][j-1];
        }
        else {
            for( int j=1; j<=m; j++ )
                ans[i][j] = ( a[i]==b[j] && ans[i-1][j-1] );
        }
    }
    return ans[n][m];
}

int main( ) {
    int n, m, i, j, l;
    char str[100];
    
    scanf( "%d%d", &n, &m );
    for( i=0; i<n; i++ ) {
        scanf( "%s", w[i] );
        len[i] = strlen( w[i] );
        code[i] = 0;
        for( j=0; w[i][j]; j++ )
        if( w[i][j] != '?' && w[i][j] != '*' )
            code[i] |= 1<<(w[i][j]-'a');
    }
    
    bool key;
    for( i=0; i<m; i++ ) {
        scanf( "%s", str );
        l = strlen( str );
        key = false;
        int c = 0;
        for( j=0; str[j]; j++ )
            c |= 1<<(str[j]-'a');
            
        for( j=0; j<n; j++ ) {
            if( (c|code[j])==c && check( w[j], len[j], str, l ) ) {
                if( key )
                    printf( " " );
                printf( "%d", j );
                key = true;
            }
        }
        if( !key )
            printf( "Not match" );
        printf( "n" );
    }
    return 0;
}