# 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;
}
```
This entry was posted in poj. Bookmark the permalink.