Cod sursa(job #3236412)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 28 iunie 2024 14:45:01
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb

#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream cin("matrix.in");
ofstream cout("matrix.out");
int n,m;
char x;
unordered_map<int,int> M;
int dp[26][1001][1001];
int suma(int i,int j,int x,int y,int l)
{
    return dp[l][x][y]-dp[l][x][j-1]-dp[l][i-1][y]+dp[l][i-1][j-1];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
           cin>>x;
           dp[x-'a'][i][j]=1;
        }
    }
    for(int l=0;l<26;l++)
      for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
           dp[l][i][j]=dp[l][i][j]+dp[l][i-1][j]+dp[l][i][j-1]-dp[l][i-1][j-1];
    for(int i=1;i<=m;i++)
      for(int j=1;j<=m;j++)
      {
        cin>>x;
        M[x-'a']++;
      }
    int ans=0;
    for(int i=1;i<=n-m+1;i++)
      for(int j=1;j<=n-m+1;j++)
      {
        bool ok=1;
        for(int l=0;l<26;l++)
        {
          int sum=suma(i,j,i+m-1,j+m-1,l);
          if(M[l]!=sum)
          {
              ok=0;
              break;
          }
        }
        if(ok)
          ans++;
      }
    cout<<ans;
    return 0;
}