1816.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:1816  User Id:fzk 
Memory:1516K  Time:718MS
Language:G++  Result:Accepted

Source 

#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;
}