Pagini recente » Cod sursa (job #1304182) | Cod sursa (job #254276) | Cod sursa (job #2349272) | Cod sursa (job #777756) | Cod sursa (job #905532)
Cod sursa(job #905532)
#include<cstdio>
#include<cstring>
#include<bitset>
#define ALPHA 97
#define NMAX 1005
using namespace std;
int N,M,frec[30],result;
bitset <NMAX> DP[NMAX];
char ch[NMAX][NMAX];
int T[NMAX][NMAX];
void read ( void )
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d\n",&N,&M);
char buf;
for(int i(1) ; i <= N; ++i && scanf("\n") )
for(int ii(1) ; ii <= N ; ++ii )
scanf("%c",&ch[i][ii]);
for(int i(1); i <= M ; ++i && scanf("\n") )
for(int ii(1); ii <= M; ++ii )
{
scanf("%c",&buf);
++frec[buf-'a'+1];
}
fclose(stdin);
}
void solve ( void )
{
//presupunem ca toate patrate N*N sunt bune
for(int i(M); i<= N; ++i)
for(int j(M) ; j<= N ;++j)
DP[i][j]=1;
//eliminam toate patrate care nu sunt bune
for(int letter = 1 ; letter <= 26; ++letter)
{
memset(T,0,sizeof(T));
for(int i(1); i <= N; ++i)
for(int ii(1); ii <= N ; ++ii )
T[i][ii]=T[i-1][ii] +T[i][ii-1]- T[i-1][ii-1]+(ch[i][ii]-'a'+1 == letter);
for(int i(M); i <= N ; ++ i)
for(int ii(M); ii <= N; ++ii )
if(DP[i][ii] && T[i][ii] - T[i][ii-M] -T[i-M][ii] +T[i-M][ii-M] != frec[letter])
DP[i][ii] = 0;
}
//numaram cate pozitii au mai rams corecte
for(int i(M); i <= N ; ++i)
for(int ii(M); ii <=N ; ++ii)
result+=( DP[i][ii] == 1) ;
}
void write ( void )
{
printf("%d\n",result);
fclose(stdout);
}
int main ( void )
{
read();
solve();
write();
return 0;
}