Cod sursă (job #401577)

#include <fstream>
using namespace std;
typedef unsigned u;

ofstream g("fotografie.out");
ifstream f("fotografie.in");
u base1[1001],base2[1001],hashes[1001];
char s[1001][1001],t[1001][1001];
int n,m,p,q;
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
    {
        f>>(t[i]+1);
    }
    f>>p>>q;
    for(int i=1; i<=p; i++)
    {
        f>>(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)
        {
            g<<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)
            {
                g<<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;
}