Pagini recente » Cod sursa (job #3282462) | Cod sursa (job #3177796) | Cod sursa (job #3262430) | Cod sursa (job #2862320) | Cod sursa (job #3264915)
#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;
}