Cod sursa(job #832725)

Utilizator elfusFlorin Chirica elfus Data 11 decembrie 2012 11:01:20
Problema Matrix Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>

char x[1024][1024], frequence[30];
int dp[1024][1024], good[1024][1024];

int main()
{
	int i, j, letter, N, M;
	char ch;
	
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	
	scanf("%d %d\n", &N, &M);
	int n = N, m = M;
	for(i=1;i<=n;++i)
        gets(x[i] + 1);
 
    for(i=1;i<=m;++i)
	{
		for(j=1;j<=m;++j)
		{
			scanf("%c", &ch);
            ++ frequence[ch - 'a'] ;
		}
		scanf("\n");
	}
	
	for (i = M; i <= N; i ++)
		for (j = M; j <= N; j ++)
			good[i][j] = true;
		
	for (letter = 0; letter <= 25; letter ++)
		for (i = 1; i <= N; i ++)
			for (j = 1; j <= N; j ++)
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
				if (x[i][j] - 'a' == letter)
					dp[i][j] ++;
				if (i >= M && j >= M)
				{
					int now = dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M];
					if (now != frequence[letter])
						good[i][j] = false;
				}
			}
	
	int sol = 0;
	for (i = M; i <= N; i ++)
		for (j = M; j <= N; j ++)
			if (good[i][j])
				sol ++;
	
	printf("%d\n", sol);
	return 0;
}