Cod sursa(job #492160)

Utilizator ChallengeMurtaza Alexandru Challenge Data 13 octombrie 2010 17:22:05
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="matrix.in";
const char OutFile[]="matrix.out";
const int MaxN=1005;

ifstream fin(InFile);
ofstream fout(OutFile);

char buffer[MaxN];
int psum[26][MaxN][MaxN],N,M,virus[26],sol,m[26];

inline int sum(int ch,int x1,int y1,int x2,int y2)
{
    return psum[ch][x2][y2]-psum[ch][x2][y1-1]-psum[ch][x1-1][y2]+psum[ch][x1-1][y1-1];
}

int main()
{
    fin>>N>>M;
    for(register int i=1;i<=N;++i)
    {
        fin>>buffer;
        for(register int j=1;j<=N;++j)
        {
            ++psum[buffer[j-1]-'a'][i][j];
        }
    }
    for(register int i=0;i<M;++i)
    {
        fin>>buffer;
        for(register int j=0;j<=M;++j)
        {
            ++virus[buffer[j]-'a'];
        }
    }
    fin.close();

    for(register int k=0;k<26;++k)
    {
        for(register int i=1;i<=N;++i)
        {
            for(register int j=1;j<=N;++j)
            {
                psum[k][i][j]+=psum[k][i-1][j]+psum[k][i][j-1]-psum[k][i-1][j-1];
            }
        }
    }

    for(register int i=M;i<=N;++i)
    {
        for(register int j=M;j<=N;++j)
        {
            bool ok=true;
            for(register int k=0;k<26;++k)
            {
                if(sum(k,i-M+1,j-M+1,i,j)!=virus[k])
                {
                    ok=false;
                    break;
                }
            }
            if(ok)
            {
                ++sol;
            }
        }
    }

    fout<<sol;
    fout.close();
    return 0;
}