Cod sursa(job #2347366)

Utilizator trifangrobertRobert Trifan trifangrobert Data 18 februarie 2019 18:36:52
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

const int NMAX = 1005;
int n, m;
char s[NMAX];
int c[NMAX][NMAX], d[NMAX][NMAX];

int main()
{
    ifstream fin("matrix.in");
    ofstream fout("matrix.out");
    fin >> n >> m;
    for (int i = 1;i <= n;++i)
    {
        fin >> (s + 1);
        for (int j = 1;j <= n;++j)
        {
            int val = (s[j] - 'a');
            c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + val;
            d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + val * val;
        }
    }
    int x = 0, y = 0;
    for (int i = 1;i <= m;++i)
    {
        fin >> (s + 1);
        for (int j = 1;j <= m;++j)
        {
            int val = (s[j] - 'a');
            x += val;
            y += val * val;
        }
    }
    int cnt = 0;
    for (int i = m;i <= n;++i)
        for (int j = m;j <= n;++j)
        {
            int a = c[i][j] - c[i - m][j] - c[i][j - m] + c[i - m][j - m];
            int b = d[i][j] - d[i - m][j] - d[i][j - m] + d[i - m][j - m];
            if (a == x && b == y)
                ++cnt;
        }
    fout << cnt << "\n";
    fin.close();
    fout.close();
    return 0;
}