Problem_10855.java

import java.util.Arrays;
import java.util.Scanner;
import java.util.BitSet;
import static java.lang.System.out;

/**
 * Exhaustive search is used here. 
 * Spent 30 mins thinking about how to optimize the nasty N^2 maxtrix traversal but to no avail.
 * So i simply submitted a brute force method and surprisingly got an AC :) 
 * 
 * time spent: 2.5 hours (maybe should have just whack and try and cut down the time spent here!)
 */
public class Main {

  
	public static void main(String[] args) {
	
		 
		 Scanner in = new Scanner(System.in);
		 while( in.hasNext() ) {
			 
			int N = in.nextInt();
			int m = in.nextInt(); // small sq
			if(N == 0) break;
			 
			 
			char[][] big 	= new char[N][N];
			char[][] small  = new char[m][m];
			 
			for(int i=0; i<N; i++)
					big[i] = in.next().toCharArray(); 
			
			for(int i=0; i<m; i++)
					small[i] = in.next().toCharArray();
			
			
			final int DIR = 4; //4 orientations. 
			int[] result = {0,0,0,0};
			
			
			for(int rotate=0; rotate<DIR; rotate++) { //traverse 4 directions 
				for(int i=0; i<N; i++) {
					for(int j=0; j<N; j++) {
						if(compare(small,big, i,j) == true)
							result[rotate]++;
					}
				}
				
				rotateRight(small); //next dir
			}
			
			
			out.print(result[0] + " " + result[1] + " " + result[2] + " " + result[3] + "\n");
			
			//rotateRight(big);
			//printMatrix(big);
			//printMatrix(small);

		 }
		 
	}//end of void main
	
	
	public static boolean compare(char[][] small, char[][] big, int row, int col ) {
		int size = small.length;
		
		
		int rowEndPt = row+size; 
		int colEndPt = col+size; 
		//out.println("s: " + size + " ("+ row + "," + col + ") rPt: " + rowEndPt + " cPt: " + colEndPt);

		// prevent scanning more than what the big matrix has!
		if(rowEndPt-1 >= big.length || colEndPt-1 >= big.length ) return false;

		// compare small and partOf(bigMatrix) 
		for(int i=row; i<rowEndPt; i++) {
			for(int j=col; j<colEndPt; j++) {
				if(big[i][j] != small[i-row][j-col]) 
					return false; 
			}
		}
		
		return true; 
	}
	
	public static void rotateRight(char[][] matrix) { 
		int cols = matrix[0].length;
		int rows = matrix.length;
		
		char[][] tmp = new char[matrix.length][matrix.length];
		
		// rotate 
		for(int i=0; i<rows; i++){
			for(int j=0; j<cols; j++) {
				tmp[j][rows-1-i] = matrix[i][j];
			}
		}
		
		// copy back 
		for(int i=0; i<rows; i++){
			for(int j=0; j<cols; j++) {
				matrix[i][j] = tmp[i][j];
			}
		}
	}
	
	
	public static void printMatrix(char[][] matrix) {
		int cols = matrix[0].length;
		int rows = matrix.length;
		
		for(int i=0; i<rows; i++){
			for(int j=0; j<cols; j++) {
				 System.out.print(matrix[i][j] + " ");
			}
			System.out.println("");
		}
	}
}//end of class main