Cod sursa(job #1307794)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 2 ianuarie 2015 20:35:18
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#define nmax 1005
#define teta 26
using namespace std;
int n,m,sol;
char a[nmax][nmax],b[nmax][nmax];
short v[nmax][nmax][26];
int k[26],x[26];

void read()
{
    ifstream f("matrix.in");
    int i,j;
    f>>n>>m;f.get();
    for (i=0;i<n;i++)
            f.getline(a[i],n+5);
    for (i=0;i<m;i++)
            f.getline(b[i],m+5);

    for (i=0;i<m;i++)
            for (j=0;j<m;j++)
                    k[b[i][j]-'a']++;

}
void adauga(int l,int c,int p)
{
    int i;
    for (i=0;i<teta;i++) x[i]+=p*v[l][c][i];
}
void trying()
{
    int i;
    for (i=0;i<teta;i++) if (x[i]!=k[i]) return;
    sol++;
}
int main(){

    int i,j,l,c;
    read();
    for (j=1;j<=n;j++)
        for (i=1;i<=n;i++) {

                for (int t=0;t<teta;t++) v[i][j][t]=v[i-1][j][t];
                v[i][j][a[i-1][j-1]-'a']++;
                if (i-m-1>=0) v[i][j][a[i-m-1][j-1]]--;
        }
    for (i=1;i<=n-m+1;i++) {
            for (j=1;j<=m;j++) {
                    adauga(i+m-1,j,1);
                    if (i-1>=1) adauga(i-1,j,-1);
            }
            trying();
            for (j=m+1;j<=n;j++) {
                    //adauga coloana urmatoare j
                    adauga(i+m-1,j,1);
                    adauga(i-1,j,-1);
                    //scad coloana trecut j-m
                    adauga(i+m-1,j-m,-1);
                    adauga(i-1,j-m,1);

                    trying();
            }
            for (j=0;j<teta;j++) x[j]=0;
    }
    ofstream g("matrix.out");
    g<<sol;
    return 0;
}