Pagini recente » Cod sursa (job #1640976) | Cod sursa (job #200288) | Cod sursa (job #1640830) | Cod sursa (job #171425) | Cod sursa (job #773963)
Cod sursa(job #773963)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
#define nmax 1000
#define Litmax 26
int n, m, mat[nmax][nmax], viz[Litmax], frec_virus[Litmax];
int dp[nmax][nmax][Litmax], a[nmax][Litmax], b[Litmax];
void citeste(){
f >> m >> n;//dim hartii genoului; dim hartii virusului
f.get();
for(int i=1; i<=m; i++){
string s;
getline(f,s);
for(int j=0; j<s.size(); j++) mat[i][j+1] = s[j]-'a';
}
for(int i=1; i<=n; i++){
string s;
getline(f,s);
for(int j=0; j<s.size(); j++) frec_virus[s[j]-'a']++;
}
}
void rezolva(){
//o aparitie in genom e daca gasesc un dreptunghi de aceelasi dimensiuni si cu aceleasi litere(nu conteaza ordinea in care apar)
//pp ca coltul dreapta jos unui dreptunghi e in (i,j)
int rez = 0;
//dp[i][j][k] = numarul de aparitii a literei k in dreptunghiul cu coltul dreapta jos in (i,j) si coltul stanga sus in (1,1)
//dp[i][j][k] = cati de k sunt pe coloana j deasupra linie i + cati de j sunt pe linia in stanga coloanei j + /
// cati de j sunt pana in dreptunghiul cu coltul dreapta jos in (i-1,j-1) si stanga sus in (1,1)
//a[j][k] = numarul de aparitii a literei k pana pe linia i si acestia sa fie doar pe coloana j
//b[k] = numarul de aparitii a literei k pana pe coloana j si acestia sa fie doar pe linia i
for(int i=1; i<=m; i++){
for(int j=1; j<=m; j++){
for(int k='a'-'a'; k<='z'-'a'; k++)a[0][k] = 0;
for(int k='a'-'a'; k<='z'-'a'; k++){
int X = 0;//daca apare si pe pozitia i,j cresc nr de aparitii
if (k == mat[i][j]) X = 1;
dp[i][j][k] = a[j][k] + b[k] + dp[i-1][j-1][k] + X;
a[j][k] = a[j][k] + X;
b[k] += X;
}
}
for(int k='a'-'a'; k<='z'-'a'; k++) b[k] = 0;
}
//acum aflu pentru fiecare litera decate ori apare in dreptunghiul 1,1; i,j folosind sume partiale
for(int i=n; i<=m; i++){
for(int j=n; j<=m; j++){
for(int k=0; k<=26; k++) viz[k] = 0;
for(int k='a'-'a'; k<='z'-'a'; k++){
viz[k] = dp[i][j][k] - dp[i-n][j][k] - dp[i][j-n][k] + dp[i-n][j-n][k];
}
int ok = 1;
for(int k=0; k<=26; k++)
if (viz[k] != frec_virus[k]) ok =0;
if (ok == 1) ++rez;
}
}
g << rez << "\n";
}
void memorie(){
int cat = 0;
cat += sizeof(mat) + sizeof(viz) + sizeof(frec_virus) + sizeof(dp) + sizeof(a) + sizeof(b);
cout << cat / 1024 << "\n";
}
int main(){
citeste();
rezolva();
//memorie();
f.close();
g.close();
return 0;
}