Cod sursa(job #3264915)

Utilizator luc3lexa_Alexandrescu Luca luc3lexa_ Data 25 decembrie 2024 18:37:21
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int nmax = 1010;

vector<int> frecv(30,0);
vector<vector<char>> mat(nmax,vector<char> (nmax,' '));
vector<vector<int>> dp(nmax,vector<int> (nmax,0)),aux(nmax,vector<int> (nmax,0));
int m,n;

void read_input(){
	fin >> m >> n;
	string aux;
	for(int i = 1; i <=m; i++){
		fin >> aux;
		for(int j = 1; j <=m; j++){
			mat[i][j] = aux[j-1];
		}
	};
	for(int i = 1; i <=n; i++){
		fin >> aux;
		for(int j = 1; j <=n; j++){
			frecv[aux[j-1]-'a'+1]++;
		}
	}
}

void solve(){
	for(int i = n; i <=m; i++){
		for(int j = n; j <=m; j++){
			dp[i][j] = 1;
		}
	}
	for(char c = 'a'; c <= 'z';c++){
	
		for(int i = 1; i <=m; i++){
			for(int j = 1; j <=m; j++){
				aux[i][j] = 0;
				aux[i][j] = (mat[i][j] == c) + aux[i-1][j] + aux[i][j-1] - aux[i-1][j-1];
			}
		}
		
		for(int i = n; i <=m; i++){
			for(int j = n; j <=m; j++){
				if(frecv[c-'a'+1] != aux[i][j] - aux[i-n][j] - aux[i][j-n] + aux[i-n][j-n]){
					dp[i][j] = 0;
				}
			}
		}
	};
	
	int ans = 0;
	for(int i = n; i <=m; i++){
		for(int j = n; j <=m; j++){
			ans += dp[i][j];
		}
	}
	fout << ans;
}
int main(){
	read_input();
	solve();
	return 0;
}