Pagini recente » Cod sursa (job #2814312) | Cod sursa (job #1526161) | Cod sursa (job #342469) | Cod sursa (job #2258487) | Cod sursa (job #1148175)
#include <fstream>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
int N, M, apv[30];
long long sol;
short ap[27][1002][1002];
char a[1002][1002], v[1002][1002];
int main()
{
f>>M>>N;
for (int i=1; i<=M; ++i) f>>(a[i]+1);
for (int i=1; i<=N; ++i)
{
f>>(v[i]+1);
for (int j=1; j<=N; ++j)
++apv[v[i][j]-'a'+1];
}
for (char c='a'; c<='z'; ++c)
for (int i=1; i<=M; ++i)
for (int j=1; j<=M; ++j)
{
if (a[i][j]==c) ap[c-'a'+1][i][j]=ap[c-'a'+1][i-1][j]+ap[c-'a'+1][i][j-1]-ap[c-'a'+1][i-1][j-1]+1;
else if (j==M) ap[c-'a'+1][i][j]=ap[c-'a'+1][i-1][j]+ap[c-'a'+1][i][j-1]-ap[c-'a'+1][i-1][j-1];
else ap[c-'a'+1][i][j]=max(ap[c-'a'+1][i-1][j], ap[c-'a'+1][i][j-1]);
}
/*for (int k=1; k<=26; ++k)
if (apv[k])
{
g<<(char)(k+96)<<'\n';
for (int i=1; i<=M; ++i && g<<'\n')
for (int j=1; j<=M; ++j)
g<<ap[k][i][j]<<' ';
}*/
for (int i=1; i<=M-N+1; ++i)
for (int j=1; j<=M-N+1; ++j)
{
bool ok=1;
for (int k=1; k<=26 && ok; ++k)
//if (apv[k])
//{
if (ap[k][i+N-1][j+N-1]-ap[k][i+N-1][j-1]-ap[k][i-1][j+N-1]+ap[k][i-1][j-1]!=apv[k])
ok=0;
//g<<(char)(k+96)<<'\n'<<i<<' '<<j<<' '<<ap[k][i+N-1][j+N-1]-ap[k][i+N-1][j-1]-ap[k][i-1][j+N-1]+ap[k][i-1][j-1]<<' '<<apv[k]<<'\n';
if (ok) ++sol;//, g<<i<<' '<<j<<'\n';
// }
}
g<<sol<<'\n';
return 0;
}