Cod sursa(job #2912526)

Utilizator euyoTukanul euyo Data 8 iulie 2022 21:49:30
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "matrix.in" );
ofstream fout( "matrix.out" );

const int DIM = 1005;
const int ALPHA = 26;

string A[DIM];
int patt[ALPHA];
char f[DIM][DIM][ALPHA];

int main() {
  int m, n;
  string s;

  fin >> m >> n;
  for ( int i = 0; i < m; ++i ) {
	fin >> A[i];
  }
  for ( int j = 0; j < m; ++j ) {
	f[0][j][A[0][j] - 'a'] = 1;
  }
  for ( int i = 1; i < m; ++i ) {
	for ( int j = 0; j < m; ++j ) {
	  for ( int ch = 0; ch < ALPHA; ++ch ) {
	    f[i][j][ch] = f[i-1][j][ch] + (ch == A[i][j] - 'a');
	  }
	}
  }
  for ( int i = 0; i < n; ++i ) {
	fin >> s;
	for ( auto ch : s ) {
	  ++patt[ch - 'a'];
	}
  }
  int res = 0;
  for ( int l1 = 0; l1 <= m - n; ++l1 ) {
	int l2 = l1 + n - 1;
    vector<int> freq(ALPHA, 0);
	for ( int c = 0; c < n; ++c ) {
	  for ( int q = 0; q < ALPHA; ++q ) {
		freq[q] += f[l2][c][q] - (l1 ? f[l1 - 1][c][q] : 0);
	  }
	}
	for ( int c = n; c < m; ++c ) {
	  bool ok = true;
      for ( int q = 0; q < ALPHA; ++q ) {
		if ( freq[q] != patt[q] ) ok = false;
		freq[q] -= (f[l2][c - n][q] - (l1 ? f[l1 - 1][c - n][q] : 0));
		freq[q] += (f[l2][c][q] - (l1 ? f[l1 - 1][c][q] : 0));
	  }
	  res += ok;
	}
	bool ok = true;
	for ( int q = 0; q < ALPHA; ++q ) {
	  if ( freq[q] != patt[q] ) ok = false;
	}
	res += ok;
  }
  fout << res;
  fin.close();
  fout.close();
  return 0;
}