1312-Where's Wally

問題概要

符号化された二次元のビット列が2つ与えられる．
ビット列を回転や反転出来るとするとき，ビット列1はビット列2に何箇所で一致するか．

解法

二次元パターンマッチング．
ラビンカープ法を二次元に適用する

実装(C++)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;
long long mod_pow(long long a,long long n,long long M){
	if(n==0)return 1;
	long long res=mod_pow(a*a%M,n/2,M);
	if(n&1)res=res*a%M;
	return res;
}
template <int B,int M>
class RollingHash{
private:
	int value;
	int hash_back;
public:
	int operator()() const{
		return value;
	}
	void set_length(int p_){
		hash_back=mod_pow(B,p_-1,M);;
	}
	explicit RollingHash(int p=0){value=0;set_length(p);}
	void add(int v){//後ろにvを追加する
		value=((long long)value*B+v)%M;
	}
	void remove(int v){
		value=(((long long)value+M-(long long)hash_back*v%M))%M;
	}
	bool operator==(const RollingHash &a){
		return a.value==value;
	}
};

int W,H,P;
char MAP[1000][1000];//検索されるもの
char PATTERN[8][100][100];//検索するもの

char tmpin[600];
inline int get_value(const char a){
	if(a>='A'&&a<='Z')return a-'A';
	if(a>='a'&&a<='z')return a-'a'+26;
	if(a>='0'&&a<='9')return a-'0'+52;
	if(a=='+')return 62;
	if(a=='/')return 63;
	cerr<<"不正な入力です:"<<a<<endl;
	return -1;
}
void rotate(int src,int dst){
	for(int x=0;x<P;x++){
		for(int y=0;y<P;y++){
			PATTERN[dst][x][y]=PATTERN[src][P-1-y][x];
		}
	}
}
void mirror(int src,int dst){
	for(int x=0;x<P;x++){
		for(int y=0;y<P;y++){
			PATTERN[dst][x][y]=PATTERN[src][y][x];
		}
	}
}
bool input(){
	scanf("%d%d%d",&W,&H,&P);
	if((W|H|P)==0)return false;
	for(int i=0;i<H;i++){
		scanf("%s",tmpin);
		for(int x=0;x<W;x+=6){
			int v=get_value(tmpin[x/6]);
			for(int k=0;k<6;k++){
				if(x+k<W){
					MAP[x+k][i]=(v>>(5-k))&1;
				}
			}
		}
	}
	for(int i=0;i<P;i++){
		scanf("%s",tmpin);
		for(int x=0;x<P;x+=6){
			int v=get_value(tmpin[x/6]);
			for(int k=0;k<6;k++){
				if(x+k<P){
					PATTERN[0][x+k][i]=(v>>(5-k))&1;
				}
			}
		}
	}
	mirror(0,4);
	for(int i=0;i<3;i++){
		rotate(i,i+1);
		rotate(4+i,4+i+1);
	}
	return true;
}
typedef RollingHash<7,35729> RH1;
typedef RollingHash<36067,1000000009> RH2;
RH1 PAT[8][100];
RH1 MAP_W[1000][1000];
int rabin_karp(int x){
	RH2 find_hash[8],exp_hash(P);
	for(int i=0;i<8;i++){
		find_hash[i].set_length(P);
	}
	int i;
	if(H<P)return 0;
	for(i=0;i<P;i++){
		for(int k=0;k<8;k++){
			find_hash[k].add(PAT[k][i]());
		}
		exp_hash.add(MAP_W[x][i]());
	}
	i=0;
	int ans=0;
	while(1){
		bool search=false;
		for(int k=0;k<8;k++){
			if(find_hash[k]==exp_hash){
				//文字列発見
				search=1;
			}
		}
		ans+=search;
		if(i>=H-P)break;
		exp_hash.remove(MAP_W[x][i]());
		exp_hash.add(MAP_W[x][i+P]());
		i++;
	}
	return ans;
}
//二次元パターンマッチング
int pattern_match(){
	for(int k=0;k<8;k++){

		for(int y=0;y<P;y++){
			RH1 tmp(P);
			for(int x=0;x<P;x++){
				tmp.add(PATTERN[k][x][y]);
			}
			PAT[k][y]=tmp;
		}
	}
	for(int y=0;y<H;y++){
		RH1 tmp(P);
		for(int x=0;x<P;x++){
			tmp.add(MAP[x][y]);
		}
		int x=0;
		while(1){
			MAP_W[x][y]=tmp;
			if(x>=W-P)break;
			tmp.remove(MAP[x][y]);
			tmp.add(MAP[x+P][y]);
			x++;
		}
	}
	int res=0;
	for(int x=0;x<=W-P;x++){
		res+=rabin_karp(x);
	}
}
int main(){
	while(input()){
		cout<<pattern_match()<<endl;

	}

}