Cod sursa(job #2120080)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 1 februarie 2018 21:21:57
Problema Matrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("matrix.in");
ofstream out("matrix.out");
const int maxn = 1005;
int fr[maxn][maxn][30];
int M[maxn][maxn];
int A[maxn][maxn];
int aux[30];
int ap[30];
int n, m;

void suma(int x1, int y1, int x2, int y2)
{
    for(int i = 0; i < 26; i++)
        aux[i] = fr[x2][y2][i] - fr[x2][y1 - 1][i] - fr[x1 - 1][y2][i] + fr[x1 - 1][y1 - 1][i];
}

int verif(int x, int y)
{
    suma(x - m + 1, y - m + 1, x, y);
    for(int i = 0; i < 26; i++)
        if(aux[i] != ap[i])
            return 0;
    return 1;
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        string s;
        in >> s;
        for(int j = 0; j < n; j++)
            M[i][j + 1] = s[j] - 'a';
    }
    for(int i = 1; i <= m; i++)
    {
        string s;
        in >> s;
        for(int j = 0; j < m; j++)
        {
            A[i][j + 1] = s[j] - 'a';
            ap[s[j] - 'a']++;
        }
    }
    /*
    for(int i = 1; i <= n; i++, cerr << "\n")
        for(int j = 1; j <= n; j++)
            cerr << M[i][j] << " ";
    cerr << "\n";
    */
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int alpha = 0; alpha < 26; alpha++)
            {
                int p = M[i][j];
                fr[i][j][alpha] = fr[i - 1][j][alpha] + fr[i][j - 1][alpha] - fr[i - 1][j - 1][alpha] + (p == alpha);
            }
        }
    }
    /*
    for(int i = 1; i <= n; i++, cerr << "\n")
        for(int j = 1; j <= n; j++)
            cerr << fr[i][j][0] << " ";
    */
    int nr = 0;
    for(int i = m; i <= n; i++)
        for(int j = m; j <= n; j++)
            if(verif(i, j))
                nr++;
    out << nr << "\n";
    return 0;
}