Cod sursa(job #3312883)

Utilizator petric_mariaPetric Maria petric_maria Data 30 septembrie 2025 17:15:06
Problema Matrix Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");

int n, m, a[1005][1005], fr[30], dp[1005][1005][30], sum[1005][1005];
string s;

int main()
{
    f >> n >> m;
    for (int i=1; i<=n; ++i) {
        f >> s;
        for (int j=0; j<s.size(); ++j)
            a[i][j+1] = s[j] - 'a';
    }
    for (int i=1; i<=m; ++i) {
        f >> s;
        for (int j=0; j<s.size(); ++j)
            fr[ s[j]-'a' ]++;
    }

    for (int c=0; c<26; ++c) {
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j)
                if (a[i][j] == c)
                    sum[i][j] = 1;
                else sum[i][j] = 0;
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j)
                sum[i][j] += (sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]);
        for (int i=m; i<=n; ++i) {
            for (int j=m; j<=n; ++j)
                dp[i][j][c] = sum[i][j] - sum[i-m][j] - sum[i][j-m] + sum[i-m][j-m];
        }

    }
    int ans = 0;
    for (int i=m; i<=n; ++i)
        for (int j=m; j<=n; ++j) {
            bool ok = true;
            for (int c=0; c<26; ++c)
                if (dp[i][j][c] != fr[c])
                    ok = false;
            if (ok)
                ans++;
        }
    g << ans;
    return 0;
}