Cod sursa(job #1148178)

Utilizator Johny_Depp22Johnny Depp Johny_Depp22 Data 20 martie 2014 15:53:02
Problema Matrix Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 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 (char c='a'; c<='z'; ++c)
        for (int i=1; i<=M; ++i)
            for (int j=1; j<=M; ++j)
            {
                ap[c-'a'+1][i][j]=ap[c-'a'+1][i-1][j]+ap[c-'a'+1][i][j-1]-ap[c-'a'+1][i-1][j-1];
                if (a[i][j]==c) ++ap[c-'a'+1][i][j];
                //if (a[i][j]==c) ap[c-'a'+1][i][j]=ap[c-'a'+1][i-1][j]+ap[c-'a'+1][i][j-1]-ap[c-'a'+1][i-1][j-1]+1;
                    //else if (j==M) ap[c-'a'+1][i][j]=ap[c-'a'+1][i-1][j]+ap[c-'a'+1][i][j-1]-ap[c-'a'+1][i-1][j-1];
                        //else ap[c-'a'+1][i][j]=max(ap[c-'a'+1][i-1][j], ap[c-'a'+1][i][j-1]);

            }

    /*for (int k=1; k<=26; ++k)
        if (apv[k])
        {
            g<<(char)(k+96)<<'\n';
            for (int i=1; i<=M; ++i && g<<'\n')
                for (int j=1; j<=M; ++j)
                    g<<ap[k][i][j]<<' ';
        }*/

    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;
}