orion3.cpp

/*
 * =====================================================================================
 *
 *       Filename:  orion.cpp
 *
 *    Description:  POJ 3690. Constellation
 *
 *        Version:  1.0
 *        Created:  07/03/2009 10:56:07 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ming Chen (chm), mingchen@cse.buaa.edu.cn
 *        Company:  BUAA.edu
 *
 * =====================================================================================
 */


#include	<iostream>

using namespace std;

const int MAXN = 1001;
const int MAXP = 51;

int num_found = 0;

inline int c2i(char c) { return c=='*' ? 1 : 0; } 

class TNode {
    public:
	TNode *children[2];
	TNode() {
	    children[0] = NULL;
	    children[1] = NULL;
	};
	~TNode() {
	    if ( children[0] != NULL ) {
		delete children[0];
		children[0] = NULL;
	    }
	    if ( children[1] != NULL ) {
		delete children[1];
		children[1] = NULL;
	    }
	};
};

TNode * insert(TNode *pnode, char *str, int n)
{
    if ( n == 0 ) return pnode;
    int idx = c2i(*str);
    if ( pnode->children[idx] == NULL ) 
	pnode->children[idx] = new TNode();
    return insert(pnode->children[idx], ++str, n-1);
}

TNode* search(TNode *pnode, char *str, int n)
{
    if ( *str == '\0' ) {
	return pnode;
    }
    if ( pnode->children[c2i(*str)] == NULL )
	return NULL;
    return search(pnode->children[c2i(*str)], str+1, n-1);
}

int main()
{
    TNode *root, *pnode;
    int N, M, T, P, Q, caseNo=1;
    char sky[MAXN][MAXN], constellation[MAXP][MAXP];

    while ( cin >> N >> M >> T >> P >> Q ) {
	num_found = 0;
	if ( N == 0 ) break;
	for (int n=0; n<N; ++n) {
	    do {
		cin.getline(sky[n], M+1);
	    } while ( sky[n][0] == '\0' );
	}

	// build trie
	root = new TNode();
	for (int n=0; n<=N-P; ++n) {
	    for (int m=0; m<=M-Q; ++m) {
		pnode = root;
		for (int p=0; p<P; ++p) {
		    pnode = insert(pnode, sky[n+p]+m, Q);
		}
	    }
	}

	// read constellation and search
	for (int t=1; t<=T; ++t) {
	    for (int p=0; p<P; ++p) {
		do {
		    cin.getline(constellation[p], Q+1);
		} while ( constellation[p][0] == '\0' );
	    }
	    pnode = root;
	    for (int p=0; p<P; ++p) {
		pnode = search(pnode, constellation[p], Q);
		if ( pnode == NULL ) break;
	    }
	    if ( pnode != NULL ) ++num_found;
	}
	cout << "Case " << caseNo++ << ": " << num_found << endl;
	delete root;
    }

    return 0;
}