Pagini recente » Cod sursa (job #1226234) | Cod sursa (job #21015) | Cod sursa (job #419688) | Cod sursa (job #912536) | Cod sursa (job #3167090)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 1001
#define alfac 130
bool ok[NMAX][NMAX];
int dp[NMAX][NMAX];
char a[NMAX][NMAX];
int vf[alfac];
int main(void){
ofstream cout("matrix.out");
ifstream cin("matrix.in");
int n, m;
cin >> n>> m;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++)cin >> a[i][j];
}
for(int i = 1;i<=m;i++)
for(int j = 1;j<=m;j++){
char x;
cin >> x;
vf[x]++;
}
for(int i = m;i<=n;i++){
for(int j = m;j<=n;j++)ok[i][j] = 1; /// presupunem ca este o potrivire
}
for(int Alfa = 'a'; Alfa <= 'z'; Alfa++){
for(int i= 1;i<=n;i++){
for(int j = 1;j<=n;j++){
dp[i][j] = (a[i][j] == Alfa) + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
}
for(int i = m;i<=n;i++){
for(int j = m;j<=n;j++){
if (dp[i][j] - dp[i-m][j] - dp[i][j-m] + dp[i-m][j-m] != vf[Alfa])
ok[i][j] = 0; /// nu este o potrivire asa ca am presupunerea noastra este gresita si o anulam
}
}
}
int ans = 0;
/// solutia este de fapt cate presupuneri corecte ne au ramas
for(int i =m;i<=n;i++)
for(int j = m;j<=n;j++)
ans += ok[i][j];
cout << ans << '\n';
}