Cod sursa(job #2832766)

Utilizator KarinAAndrei Karina KarinA Data 14 ianuarie 2022 11:37:53
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int n,m,cnt;
int f[26],a[26];
int dp[1001][1001][26];

void citire()
{
    int i,j,k;
    char ch;
    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            in>>ch;
            dp[i][j][ch-'a']++;
        }
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
        {
            in>>ch;
            f[ch-'a']++;
        }
}
void solve()
{
    int i,j,k;
    bool ok;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=0;k<=25;k++)
                dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k]+dp[i][j-1][k]-dp[i-1][j-1][k];
    for(i=m;i<=n;i++)
        for(j=m;j<=n;j++)
        {
            ok=1;
            for(k=1;k<=25 && ok!=0;k++)
            {
                a[k]=dp[i][j][k]-dp[i-m][j][k]-dp[i][j-m][k]+dp[i-m][j-m][k];
                if(a[k]!=f[k])
                    ok=0;
            }
            if(ok)
                cnt++;
        }
    out<<cnt;
}

int main()
{
    citire();
    solve();
    return 0;
}