Cod sursa(job #855127)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 14 ianuarie 2013 17:58:28
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#define val 1009
using namespace std;

ifstream f("matrix.in");
ofstream g("matrix.out");

int n , m , i , j , k , h , c,sol;
char V[val][val] , a[val];
int Z[val][val];
int Ok[val][val];
int Fr[300];
int main(){
    f>>m>>n;
    sol=(m-n+1)*(m-n+1);
    for(i=1;i<=m;i++){       
        f>>V[i]+1;     
    }   
    for(i=1;i<=n;i++){       
        f>>a+1;
        for(j=1;j<=n;j++)
            Fr[a[j]]++;     
    }
    for(i='a';i<='z';i++){
        if(Fr[i]==0)
            continue;
        for(j=1;j<=m;j++){
            for(k=1;k<=m;k++){
                Z[j][k]=Z[j-1][k]+Z[j][k-1]-Z[j-1][k-1];
                if(V[j][k]==i)
                    Z[j][k]++;
                if(j>=n&&k>=n&&Ok[j][k]==0){
                    h=Z[j][k]-Z[j][k-n]-Z[j-n][k]+Z[j-n][k-n];
                    if(h!=Fr[i]){
                        if(Ok[j][k]==0)
                            sol--;
                        Ok[j][k]=1;                     
                    }
                }
            }           
        }
    }
    g<<sol;
    return 0;
}