Cod sursă (job #546379)

#include <fstream>
using namespace std;
typedef unsigned u;
ofstream fout("fotografie.out");
ifstream fin("fotografie.in");
u base1[1001], base2[1001], hashes[1001];
char s[1001][1001], t[1001][1001];
int n, m, p, q;


int main()
{
	fin>>n>>m;
	
	for(int i=1; i<=n; i++)
		fin>>(t[i]+1);
		
	fin>>p>>q;
	for(int i=1; i<=p; i++)
		fin>>(s[i]+1);
		
	base1[0]=base2[0]=1;
	
	for(int i=1; i<=1000; i++)
	{
		base1[i]=base1[i-1]*137;
		base2[i]=base2[i-1]*29989;
	}
	
	u hashpattern=0;

	for(int j=1; j<=m; j++)
		for(int i=1; i<=p; i++)
			hashes[j]=hashes[j]*137+t[i][j];
			
	for(int j=1; j<=q; j++)
	{
		u code=0;
		for(int i=1; i<=p; i++)
		code=code*137+s[i][j];
		hashpattern=hashpattern*29989+code;
	}

	for(int i=1; i+p-1<=n; i++)
	{
		u hashtext=0;
		for(int j=1; j<=q; j++)
			hashtext=hashtext*29989+hashes[j];

		if(hashtext==hashpattern)
			fout<<i-1<<' '<<0<<'\n';
	
		for(int j=q+1; j<=m; j++)
		{
			hashtext=(hashtext*29989+hashes[j]-base2[q]*hashes[j-q]);
			if(hashtext==hashpattern)
			out<<i-1<<' '<<j-q<<'\n';
		}
		
		for(int j=1; j<=m; j++)
			hashes[j]=(hashes[j]*137+t[i+p][j]-base1[p]*t[i][j]);
	}

	return 0;
}