Cod sursa(job #1148181)

Utilizator Johny_Depp22Johnny Depp Johny_Depp22 Data 20 martie 2014 15:55:07
Problema Matrix Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");

int N, M, apv[30];
long long sol;
short ap[27][1002][1002];
char a[1002][1002], v[1002][1002];

int main()
{
    f>>M>>N;
    for (int i=1; i<=M; ++i) f>>(a[i]+1);
    for (int i=1; i<=N; ++i)
    {
        f>>(v[i]+1);
        for (int j=1; j<=N; ++j)
            ++apv[v[i][j]-'a'+1];
    }

    for (int k=1; k<=26; ++k)
        for (int i=1; i<=M; ++i)
            for (int j=1; j<=M; ++j)
                if (apv[k])
                ap[k][i][j]=ap[k][i-1][j]+ap[k][i][j-1]-ap[k][i-1][j-1]+(a[i][j]==(char)(k+96));

    for (int i=1; i<=M-N+1; ++i)
        for (int j=1; j<=M-N+1; ++j)
        {
            bool ok=1;
            for (int k=1; k<=26 && ok; ++k)
                //if (apv[k])
                //{
                    if (ap[k][i+N-1][j+N-1]-ap[k][i+N-1][j-1]-ap[k][i-1][j+N-1]+ap[k][i-1][j-1]!=apv[k])
                        ok=0;
                    //g<<(char)(k+96)<<'\n'<<i<<' '<<j<<' '<<ap[k][i+N-1][j+N-1]-ap[k][i+N-1][j-1]-ap[k][i-1][j+N-1]+ap[k][i-1][j-1]<<' '<<apv[k]<<'\n';
                    if (ok) ++sol;//, g<<i<<' '<<j<<'\n';
               // }

        }
    g<<sol<<'\n';
    return 0;
}