Pagini recente » Statistici Misha Sofy (Misha_Sofy) | Istoria paginii runda/iconcurs3 | Cod sursa (job #2741870) | Istoria paginii runda/cls_11_simulare_oji/clasament | Cod sursa (job #774091)
Cod sursa(job #774091)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
#define nmax 1005
#define Sigma 27
int mat[nmax][nmax], n, m, frec_virus[Sigma+'a'], dp[nmax][nmax];
bool in_regula[nmax][nmax];
void citeste(){
f >> m >> n;//dimen genomului; dimen 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];
}
for(int i=1; i<=n; i++){
string s;
getline(f,s);
for(int j=0; j<s.size(); j++) ++frec_virus[s[j]];
}
}
void nr_aparitii(int k){
//nr de aparitii a literi k pana pe pozitia (i,j)
for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) dp[i][j]=0;
for(int i=1; i<=m; i++){
for(int j=1; j<=m; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];
if (k == mat[i][j]) ++dp[i][j];
}
}
}
void check(int k){
//fac o matrice in_regula[i][j] = care imi zice daca dreptunghiul cu coltul dreapta jos in (i,j) are aceelasi litere ca si virusul(nu conteaza ordinea)
for(int i=n; i<=m; i++){
for(int j=n; j<=m; j++){
int X = dp[i][j] - dp[i-n][j] - dp[i][j-n] + dp[i-n][j-n];
if (X != frec_virus[k]) in_regula[i][j] = 0;
else if (X == frec_virus[k]) in_regula[i][j] = 1;
}
}
}
void rezolva(){
//fac acum numarul de a aparitii a literei a,b,c
for(int k='a'; k<='z'; k++){
nr_aparitii(k);
check(k);
}
int rez = 0;
for(int i=n; i<=m; i++){
for(int j=n; j<=m; j++){
rez += in_regula[i][j];
}
}
//cout << rez << "\n";
g << rez << "\n";
}
void memorie(){
int sum = 0;
sum = sizeof(in_regula)+ sizeof(dp)+sizeof(mat)+sizeof(frec_virus);
cout << sum/1024 << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}