Pagini recente » Cod sursa (job #1089302) | Cod sursa (job #1386740) | Cod sursa (job #2536732) | Cod sursa (job #656965) | Cod sursa (job #843916)
Cod sursa(job #843916)
/* Intai se calculeaza frecventa fiecarei litere in matricea virus de dimensiune N*N.
Vom verifica pentru toate cele (M-N)*(M-N) matrici posibile daca sunt sau nu permutari ale matricii-virus.
Pentru fiecare litera a alfabetului, construim matricea B ale carei elemente Bi,j = numarul de aparitii pe pozitii (x, y) cu 1 ≤ x ≤ i si 1 ≤ y ≤ j ale literei cautate.
Relatia de recurenta este Bi,j = Bi-1,j+Bi,j-1-Bi-1,j-1, la care se adauga 1 daca si numai daca pe pozitia (i, j) se afla litera pe care o cautam.
In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in (i-N+1, j-N+1) si (i, j) este Bi,j-Bi-N,j-Bi,j-N+Bi-N,j-N .
Pe langa matricea B (in care se efectueaza preprocesarea pentru litera curenta) mai folosim matricea W in care tinem minte daca pentru o anumita pozitie
s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit.
*/
#include<fstream>
using namespace std;
ifstream f("matrix.in"); ofstream g("matrix.out");
const int dim=1002;
int n, m, i, j, x, y, total, nrapar;
int A[dim][dim], B[dim][dim], Nr[30];
bool W[dim][dim];
char ch;
int main ()
{ f>>m>>n;
for(i=1; i<=m; ++i)
for(j=1; j<=m; ++j)
f>>ch, A[i][j]=ch-'a'+1;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
f>>ch, Nr[ch-'a'+1]++;
for(i=1; i<=26; ++i)
{ for(x=1; x<=m; ++x)
for(y=1; y<=m; ++y)
B[x][y]=0;
for(x=1; x<=m; ++x)
for(y=1; y<=m; ++y)
{
if(i==A[x][y]) ++B[x][y];
B[x][y]+=-B[x-1][y-1]+B[x-1][y]+B[x][y-1];
}
for(x=n; x<=m; ++x)
for(y=n; y<=m; ++y)
{
nrapar=B[x][y]-B[x-n][y]+B[x-n][y-n]-B[x][y-n];
if(nrapar!=Nr[i]) W[x][y]=true;
}
}
for(i=n;i<=m;++i)
for(j=n;j<=m;++j)
if(!W[i][j]) ++total;
g<<total<<"\n";
return 0;
}