POJ 3690 找星座（2D匹配）（未解答）
POJ 3690 找星座（2D匹配）（未解答）
Michael阿明
发布于 2021-02-20 10:46:32
发布于 2021-02-20 10:46:32
文章被收录于专栏：Michael阿明学习之路
1. 题目信息
1.1 题目链接
http://poj.org/problem?id=3690
1.2 题目大意
给定大的矩阵（天空的样子），然后给定若干小矩阵（可能的天空的一角） 求有多少个小矩阵是从大矩阵里抠出来的（2D匹配）
1.3 解题思路
采用RK算法，求矩阵的哈希值，看哈希值是否一样，若一样，再比较一下看是否真的一样（防止哈希冲突）
2. 代码
2.1 Time Limit Exceeded 代码
在这里插入图片描述
计算的是整体矩阵的哈希值
/**
* @description: poj3690 2维矩阵匹配
* @author: michael ming
* @date: 2019/6/25 19:47
* @modified by:
*/
#include <iostream>
#include <math.h>
using namespace std;
int a[1001][1001];
int b[51][51];
typedef unsigned long long ull;
ull cal_hash_b(int r, int c, int b[][51])
{
int i, j, k;
ull value = 0;
for (i = 0; i < r; ++i) //计算2d模式串的hash值value
{
for(j = 0, k = 1; j < c; ++j,++k)
value += b[i][j]*pow(2.0,k);
}
return value;
}
ull cal_hash_a_child(int i0, int j0, int r, int c, int a[][1001])
{
int i, j, k;
ull hash_value = 0;
for (i = i0; i < r; ++i) //计算2d子串的hash值value
{
for(j = j0, k = 1; j < c; ++j,++k)
hash_value += a[i][j]*pow(2.0,k);
}
return hash_value;
}
bool same(int a[][1001], int b[][51], int i0, int j0, int mr, int mc)
{
int x = i0, y = j0, i, j;
for(i = 0; i < mr; ++i,++x)
{
for(j = 0, y = j0; j < mc; ++j,++y)//记得写y=j0,换行后y复位
{
if(a[x][y] != b[i][j])
return false;
}
}
return true;
}
int str_RK_2d(int a[][1001], int nr, int nc, int b[][51], int mr, int mc)//s是主串，t是模式串
{
int i, j;
ull hash_val, value;
value = cal_hash_b(mr,mc,b);//计算2d模式串哈希值
for(i = 0; i < nr-mr+1; ++i)//行最多nr-mr+1次比较
{
for(j = 0; j < nc-mc+1; ++j)//列最多nc-mc+1次比较
{
hash_val = cal_hash_a_child(i,j,mr+i,mc+j,a);//计算2d子串哈希值
if(hash_val == value && same(a,b,i,j,mr,mc))
{//如果2d子串哈希值等于模式串的，且"真的"字符串匹配（避免冲突带来的假匹配）
return 1;
}
}
}
return 0;
}
void creatMatrix_a(int a[][1001], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
cin >> ch;
if(ch == '*')
a[i][j] = 1;
else
a[i][j] = 0;
}
}
void creatMatrix_b(int b[][51], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
cin >> ch;
if(ch == '*')
b[i][j] = 1;
else
b[i][j] = 0;
}
}
int main()
{
int N, M, T, P, Q, count, ID = 1;
while(cin >> N >> M >> T >> P >> Q && N)
{
count = 0;
creatMatrix_a(a,N,M);
while(T--)
{
creatMatrix_b(b,P,Q);
count += str_RK_2d(a,N,M,b,P,Q);
}
cout << "Case " << ID++ << ": " << count << endl;
}
return 0;
}2.2 Time Limit Exceeded 代码
优化了哈希值的计算方式，采用错位乘以2的方式，2的k次幂提前算好(还试了改成位运算)，都是超时
/**
* @description: poj3690 2维矩阵匹配
* @author: michael ming
* @date: 2019/6/25 19:47
* @modified by:
*/
#include <iostream>
using namespace std;
typedef unsigned long long ull;
int a[1001][1001];
int b[51][51];
ull cal_hash_b(int r, int c, int b[][51])
{
int i, j, k;
ull value = 0;
for (i = 0; i < r; ++i) //计算2d模式串的hash值value
{
for(j = 0, k = c-1; j < c; ++j,--k)
{
value += b[i][j]<<k;
}
}
return value;
}
ull cal_hash_a_child(int i0, int j0, int r, int c, int a[][1001])
{
int i, j, k;
ull hash_value = 0;
for (i = i0; i < r; ++i) //计算2d子串的hash值value
{
for(j = j0, k = c-1; j < c; ++j,--k)
hash_value += a[i][j]<<k;
}
return hash_value;
}
bool same(int a[][1001], int b[][51], int i0, int j0, int mr, int mc)
{
int x = i0, y = j0, i, j;
for(i = 0; i < mr; ++i,++x)
{
for(j = 0, y = j0; j < mc; ++j,++y)//记得写y=j0,换行后y复位
{
if(a[x][y] != b[i][j])
return false;
}
}
return true;
}
int sum(int a[][1001], int i0, int j0, int mr)
{
int sum = 0;
for(int x = 0; x < mr; ++x,++i0)
sum += a[i0][j0];
return sum;
}
int str_RK_2d(int a[][1001], int nr, int nc, int b[][51], int mr, int mc)//s是主串，t是模式串
{
int i, j;
ull hash_val, value;
value = cal_hash_b(mr,mc,b);//计算2d模式串哈希值
for(i = 0; i < nr-mr+1; ++i)//行最多nr-mr+1次比较
{
for(j = 0; j < nc-mc+1; ++j)//列最多nc-mc+1次比较
{
if(j == 0)
hash_val = cal_hash_a_child(i,j,mr+i,mc+j,a);//计算2d子串哈希值
else
hash_val = ((hash_val-(sum(a,i,j,mr)<<(mc-1)))<<1) + sum(a,i,j+mc-1,mr);
if(hash_val == value && same(a,b,i,j,mr,mc))
{//如果2d子串哈希值等于模式串的，且"真的"字符串匹配（避免冲突带来的假匹配）
return 1;
}
}
}
return 0;
}
void creatMatrix_a(int a[][1001], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
cin >> ch;
if(ch == '*')
a[i][j] = 1;
else
a[i][j] = 0;
}
}
void creatMatrix_b(int b[][51], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
cin >> ch;
if(ch == '*')
b[i][j] = 1;
else
b[i][j] = 0;
}
}
int main()
{
int N, M, T, P, Q, count, ID = 1;
while(cin >> N >> M >> T >> P >> Q && N)
{
count = 0;
creatMatrix_a(a,N,M);
while(T--)
{
creatMatrix_b(b,P,Q);
count += str_RK_2d(a,N,M,b,P,Q);
}
cout << "Case " << ID++ << ": " << count << endl;
}
return 0;
}2.3 Time Limit Exceeded 代码
改为计算每行的哈希值，把大矩阵的所有小矩阵的宽度的每行哈希值算出来，后面开始逐行比较，有不符合的，跳出，寻找下一个，还是超时
/**
* @description: poj3690 2维矩阵匹配
* @author: michael ming
* @date: 2019/6/25 19:47
* @modified by:
*/
#include <time.h>
#include <stdio.h>
typedef unsigned long long ull;
int a[1001][1001];
int b[51][51];
ull hash_b[51];//存放每行的哈希值，每行相当于一个2进制数
ull hash_a[1001][1001];//存放主串子串的哈希值
void cal_hash_b(int r, int c, int b[][51])
{
int i, j, k;
ull value;
for (i = 0; i < r; ++i) //计算2d模式串的hash值value
{
value = 0;
for(j = 0, k = c-1; j < c; ++j,--k)
{
value += b[i][j]<<k;
}
hash_b[i] = value;
}
return;
}
void cal_hash_a_child(int N, int M, int a[][1001], int P, int Q)
{
int i, j, k, x;
ull hash_value;
for (i = 0; i < N; ++i) //计算2d子串的每行的hash值
{
for(j = 0; j < M-Q+1; ++j)
{
if(j == 0)
{
hash_value = 0;
for(x = j, k = Q-1; x < j+Q && k >= 0; ++x,--k)
hash_value += a[i][x]<<k;
}
else
hash_value = ((hash_a[i][j-1]-(a[i][j-1]<<(Q-1)))<<1)+a[i][j+Q-1];
hash_a[i][j] = hash_value;
}
}
}
int str_RK_2d(int a[][1001], int N, int M, int b[][51], int P, int Q)//s是主串，t是模式串
{
int i, j, k, x;
bool flag = false;
cal_hash_b(P,Q,b);//计算2d模式串每行哈希值
for(j = 0; j < M-Q+1; ++j)//列最多nc-mc+1次比较,分别比较每行，列先固定
{
for(i = 0; i < N-P+1; ++i)
{//行最多nr-mr+1次比较
for(x = i, k = 0; x < i+P && k < P; ++x,++k)
{//一组比较P行
if(hash_a[x][j] == hash_b[k])//比较子串哈希值
flag = true;
else
{
flag = false;
break;
}
}
if(flag == true)
return 1;
}
}
return 0;
}
void creatMatrix_a(int a[][1001], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
ch = getchar();
while(ch == ' '||ch == '\n')
ch = getchar();
if(ch == '*')
a[i][j] = 1;
else
a[i][j] = 0;
}
}
void creatMatrix_b(int b[][51], int r, int c)
{
int i, j;
char ch;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
{
ch = getchar();
while(ch == ' '||ch == '\n')
ch = getchar();
if(ch == '*')
b[i][j] = 1;
else
b[i][j] = 0;
}
}
int main()
{
// clock_t start, finish;
// start = clock();
int N, M, T, P, Q, count, ID = 1;
while((scanf("%d%d%d%d%d",&N,&M,&T,&P,&Q)!=EOF) && N)
{
count = 0;
creatMatrix_a(a,N,M);
cal_hash_a_child(N,M,a,P,Q);
while(T--)
{
creatMatrix_b(b,P,Q);
count += str_RK_2d(a,N,M,b,P,Q);
}
printf("Case %d: %d\n",ID++,count);
}
// finish = clock();
// cout << "takes "<< finish-start << " ms." << endl;
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/06/26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
