Cod sursa(job #1824959)

Utilizator greenadexIulia Harasim greenadex Data 8 decembrie 2016 16:53:26
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "matrix",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MAX = 1e3 + 5, SIGMA = 26;

int n, m;
int matrix[MAX][MAX];
int cnt[SIGMA];
int dp[MAX][MAX];
bool ok[MAX][MAX];

int main() {
	fin >> n >> m;
	string row;
	for (int i = 1; i <= n; i++) {
		fin >> row;
		for (int j = 0; j < n; j++) {
			matrix[i][j + 1] = row[j] - 'a';
		}
	}

	for (int i = 0; i < m; i++) {
		fin >> row;
		for (char letter : row) {
			cnt[letter - 'a']++;
		}
	}

	for (int letter = 0; letter < SIGMA; letter++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
				if (matrix[i][j] == letter) {
					dp[i][j]++;
				}
			}
		}
		
		for (int i = m; i <= n; i++) {
			for (int j = m; j <= n; j++) {
				int x1 = i - m, y1 = j - m;
				if (dp[i][j] + dp[x1][y1] - dp[x1][j] - dp[i][y1] != cnt[letter]) {
					ok[i][j] = 1;
				}
			}
		}
	}

	int cnt = 0;
	for (int i = m; i <= n; i++) {
		for (int j = m; j <= n; j++) {
			cnt += (1 - ok[i][j]);
		}
	}

	fout << cnt;
	return 0; 
}