Cod sursa(job #761055)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 24 iunie 2012 16:14:47
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<string.h>
#define NMAX 506
#define MMAX 102
int M1[ NMAX ][ NMAX ], M2[ MMAX ][ MMAX ], A[ NMAX ][ NMAX ], B[ MMAX ][ MMAX ], C[ NMAX ][ NMAX ], L[ MMAX ][ MMAX ], n, m, nr;
void read()
{
	int i, j;
	FILE *f = fopen("tetris2.in", "r");
	fscanf(f, "%d", &n);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			fscanf(f, "%d", &M1[i][j]), A[i][j-1] = M1[i][j-1] - M1[i][j];
	fscanf(f, "%d", &m);
	for(i = 1; i <= m; i++)
		for(j = 1; j <= m; j++)
			fscanf(f, "%d", &M2[i][j]), B[i][j-1] = M2[i][j] - M2[i][j-1];
	fclose(f);
	if(m == 1)
		nr = n * n;
}
void Prefix(int l)
{
	int k, i;
	L[l][1] = 0;
	for(i = 2; i < m; i++)
	{
		k = L[l][i-1];
		while(k && B[l][k+1] != B[l][i])
			k = L[l][k];
		if(B[l][k+1] == B[l][i])
			k++;
		L[l][i] = k;
	}
}
void KMP(int l1, int l2)
{
	int i, k = 0;
	for(i = 1; i <= n; i++)
	{
		while(k > 0 && B[l2][k+1] != A[l1][i])
			k = L[l2][k];
		if(B[l2][k+1] == A[l1][i])
			k++;
		if(k == m - 1)
		{
			C[l1][i - m + 1] = 1;
			k = L[l2][k];
		}
	}
}
void solve()
{
	int i, q, l, c, s;
	for(i = 1; i <= m; i++)
		Prefix(i);
	for(i = 1; i <= n - m + 1; i++)
	{
		memset(C, 0, sizeof(C));
		for(q = 1; q <= m; q++)
			KMP(i + q - 1, q);
		for(c = 1; c <= n - m + 1; c++)
		{
			if(C[i][c])
			{
				s = 1, l = i + 1;
				while(C[l][c])
					s++, l++;
				if(s == m)
					nr++;
			}
		}
	}
}
void write()
{
	FILE *g = fopen("tetris2.out", "w");
	fprintf(g, "%d\n", nr);
	fclose(g);
}
int main()
{
	read();
	if(!nr)
		solve();
	write();
	return 0;
}