[poj] 3690 Constellations || 矩阵hash

原题

在大矩阵里找有几个小矩阵出现过，多组数据

将t个矩阵hash值放入multiset，再把大矩阵中每个hash值从multiset里扔出去，这样最后剩在multiset里的值就是没有找到的小矩阵，答案就是t-size了。

矩阵hash：

a[i][j]为以i,j为右下角的长为p，宽为q的hash值。

先处理横行的hash，然后再把横行的hash值hash，这样就得到了矩阵的hash值。（注意行和列的base要不一样，不然很容易WA）

#include<cstdio>

#include<set>

typedef unsigned long long ll;

#define ba1 1314

#define ba2 100000007

#define T 1010

#define P 55

using namespace std;

ll a[T][T],b[T][T],base1[T],base2[T];

int n,m,t,p,q,cnt;

char ac[T][T],chk[2*P][T][T];

void init()

{

    base1[0]=1;

    base2[0]=1;

    for (int i=1;i<=1000;i++)

    {

	base1[i]=base1[i-1]*ba1;

	base2[i]=base2[i-1]*ba2;

    }

}

void count(char s[][T],int x,int y)

{

    for (int i=1;i<=x;i++)

    {

	for (int j=1;j<=q;j++)

	    b[i][j]=(j==1)?s[i][j]:(b[i][j-1]*ba1+s[i][j]);

	for (int j=q+1;j<=y;j++)

	    b[i][j]=b[i][j-1]*ba1+s[i][j]-s[i][j-q]*base1[q];

    }

    for (int j=q;j<=y;j++)

    {

	for (int i=1;i<=p;i++)

	    a[i][j]=(i==1)?b[i][j]:(a[i-1][j]*ba2+b[i][j]);

	for (int i=p+1;i<=x;i++)

	    a[i][j]=a[i-1][j]*ba2+b[i][j]-b[i-p][j]*base2[p];

    }

}

int solve()

{

    multiset<ll> s;

    for (int i=1;i<=t;i++)

    {

	count(chk[i],p,q);

	s.insert(a[p][q]);

    }

    count(ac,n,m);

    for (int i=p;i<=n;i++)

	for (int j=q;j<=m;j++)

	    s.erase(a[i][j]);

    return t-s.size();

}

int main()

{

    init();

    while (~scanf("%d%d%d%d%d",&n,&m,&t,&p,&q) && n+m+t+p+q)

    {

	++cnt;

	for (int i=1;i<=n;i++) scanf("%s",ac[i]+1);

	for (int i=1;i<=t;i++)

	    for (int j=1;j<=p;j++)

		scanf("%s",chk[i][j]+1);

	printf("Case %d: %d\n",cnt,solve());

    }

    return 0;

}

巴特西

[poj] 3690 Constellations || 矩阵hash

原题

最新文章

热门文章