Cod sursa(job #3368489)

Utilizator PortallosAlexandru Vladimir Portallos Data 14 octombrie 2026 20:48:56
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

int n, m;
char mat[1001][1001];
char virus[1001][1001];
int sumeleVirusului[27];

int sums[1001][1001];
bitset<1001> remaining[1001];
int Max = INT_MIN;

int sumDrept(int starti, int startj, int endi, int endj){
    return sums[endi][endj] - sums[starti-1][endj] - sums[endi][startj-1] + sums[starti-1][startj-1];
}

int main() {
    
    fin>>n>>m;
    for(int i = 1; i <= n; i++){
        string s;
        fin>>s;
        for(int j = 1; j <= n; j++){
            mat[i][j] = s[j-1];
        }
    }
    
    for(int i = 1; i <= m; i++){
        string s;
        fin>>s;
        for(int j = 1; j <= m; j++){
            virus[i][j] = s[j-1];
        }
    }
    
    for(int i = 1; i <= n; i++){
        remaining[i].set();
    }
    
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= m; j++){
            sumeleVirusului[virus[i][j] - 'a' + 1]++;
        }
    }
    
    for(char litera = 'a'; litera <= 'z'; litera++){
            
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i-1][j-1] + (int)(litera == mat[i][j]);
            }
        }   
        
        for(int i = m; i <= n; i++){
            for(int j = m; j <= n; j++){
                if(sumDrept(i-m+1, j-m+1, i, j) != sumeleVirusului[litera - 'a' + 1])
                    remaining[i][j] = 0;
            }
        }  
        
    }
    
    int cnt = 0;
    for(int i = m; i <= n; i++){
        for(int j = m; j <= n; j++){
            cnt+=(int)remaining[i][j];
        }
    }
    

    fout<<cnt;
    
    return 0;
}