Cod sursa(job #575852)

Utilizator Catah15Catalin Haidau Catah15 Data 8 aprilie 2011 20:03:25
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;

#define maxN 1005


char a[maxN][maxN];
int vir[30], v[30], sol, N, M;
int cont[maxN][30];


int main()
{
	ifstream f("matrix.in");
	ofstream g("matrix.out");
	
	f >> N >> M;
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= N; ++ j)
		{	
			f >> a[i][j];
			
			if (i <= M)
				++ cont[j][a[i][j] - 'a'];
		}
	
	for (int i = 1; i <= M; ++ i)
		for (int j = 1; j <= M; ++ j)
		{
			char c;
			
			f >> c;
			
			++ vir[c - 'a'];
		}
	

	
	
	for (int i = 1; i <= N - M + 1; ++ i)
	{
		memset (v, 0, sizeof (v));
		
		bool ok = true;
		
		
		for (int j = 1; j <= M; ++ j)
			for (int t = 0; t < 26; ++ t)
				v[t] += cont[j][t];
		
		
		for (int t = 0; t < 26; ++ t)
			if (v[t] != vir[t])
			{
				ok = false;
				break;
			}
		
		if (ok) ++ sol;
		
		
		
		for (int j = 2; j <= N - M + 1; ++ j)
		{
			for (int t = 0; t < 26; ++ t)
				v[t] -= cont[j - 1][t] ;
			
			for (int t = 0; t < 26; ++ t)
				v[t] += cont[j + M - 1][t];
			
			ok = true;
			
			for (int t = 0; t < 26; ++ t)
				if (v[t] != vir[t])
				{
					ok = false;
					break;
				}
			
			if (ok) ++ sol;
		}
		
		
		for (int j = 1; j <= N; ++ j)
		{	
			-- cont[j][a[i][j] - 'a'];
			++ cont[j][a[i + M][j] - 'a'];
		}
	}

	
	g << sol;
	
	
	f.close();
	g.close();
	
	return 0;
}