Pagini recente » Cod sursa (job #3356568) | Monitorul de evaluare | Cod sursa (job #318858) | Cod sursa (job #3308577) | Cod sursa (job #3312883)
#include <bits/stdc++.h>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
int n, m, a[1005][1005], fr[30], dp[1005][1005][30], sum[1005][1005];
string s;
int main()
{
f >> n >> m;
for (int i=1; i<=n; ++i) {
f >> s;
for (int j=0; j<s.size(); ++j)
a[i][j+1] = s[j] - 'a';
}
for (int i=1; i<=m; ++i) {
f >> s;
for (int j=0; j<s.size(); ++j)
fr[ s[j]-'a' ]++;
}
for (int c=0; c<26; ++c) {
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
if (a[i][j] == c)
sum[i][j] = 1;
else sum[i][j] = 0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
sum[i][j] += (sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]);
for (int i=m; i<=n; ++i) {
for (int j=m; j<=n; ++j)
dp[i][j][c] = sum[i][j] - sum[i-m][j] - sum[i][j-m] + sum[i-m][j-m];
}
}
int ans = 0;
for (int i=m; i<=n; ++i)
for (int j=m; j<=n; ++j) {
bool ok = true;
for (int c=0; c<26; ++c)
if (dp[i][j][c] != fr[c])
ok = false;
if (ok)
ans++;
}
g << ans;
return 0;
}