Cod sursa(job #1827741)

Utilizator SaitamaSaitama-san Saitama Data 12 decembrie 2016 11:27:53
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int nMax = 1005;
char a[nMax][nMax], b[nMax][nMax];
long long S[nMax][nMax], SP[nMax][nMax];
int n, m, ans;
long long s, sp;

inline void Read()
{
    int i;
    fin >> n >> m;
    for(i = 1; i <= n; i++)
        fin >> (a[i] + 1);
    for(i = 1; i <= m; i++)
        fin >> (b[i] + 1);
}

inline void Solve()
{
    int i, j;
    long long v, vp;
    for(i = 1; i <= m; i++)
        for(j = 1; j <= m; j++)
        {
            s += (b[i][j] - 'a' + 1);
            sp += ((b[i][j] - 'a' + 1) * (b[i][j] - 'a' + 1));
        }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            S[i][j] = (a[i][j] - 'a' + 1) + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
            SP[i][j] = (a[i][j] - 'a' + 1) * (a[i][j] - 'a' + 1) + SP[i - 1][j] + SP[i][j - 1] - SP[i - 1][j - 1];
        }
    for(i = m; i <= n; i++)
        for(j = m; j <= n; j++)
        {
            v = S[i][j] - S[i - m][j] - S[i][j - m] + S[i - m][j - m];
            vp = SP[i][j] - SP[i - m][j] - SP[i][j - m] + SP[i - m][j - m];
            if(v == s && vp == sp) ans++;
        }
    fout << ans << "\n";
}

int main()
{
    Read();
    Solve();
    fin.close();fout.close();
    return 0;
}