网站建设搜索代码,网站如何设计方案,项目外包app,大什么的网站建设公司好文章目录1. 题目信息1.1 题目链接1.2 题目大意1.3 解题思路2. 代码2.1 Time Limit Exceeded 代码2.2 Time Limit Exceeded 代码2.3 Time Limit Exceeded 代码1. 题目信息
1.1 题目链接
http://poj.org/problem?id3690
1.2 题目大意
给定大的矩阵#xff08;天空的样子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)//记得写yj0,换行后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-mr1; i)//行最多nr-mr1次比较{for(j 0; j nc-mc1; j)//列最多nc-mc1次比较{hash_val cal_hash_a_child(i,j,mri,mcj,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;elsea[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;elseb[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)//记得写yj0,换行后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-mr1; i)//行最多nr-mr1次比较{for(j 0; j nc-mc1; j)//列最多nc-mc1次比较{if(j 0)hash_val cal_hash_a_child(i,j,mri,mcj,a);//计算2d子串哈希值elsehash_val ((hash_val-(sum(a,i,j,mr)(mc-1)))1) sum(a,i,jmc-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;elsea[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;elseb[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-Q1; j){if(j 0){hash_value 0;for(x j, k Q-1; x jQ k 0; x,--k)hash_value a[i][x]k;}elsehash_value ((hash_a[i][j-1]-(a[i][j-1](Q-1)))1)a[i][jQ-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-Q1; j)//列最多nc-mc1次比较,分别比较每行列先固定{for(i 0; i N-P1; i){//行最多nr-mr1次比较for(x i, k 0; x iP 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;elsea[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;elseb[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;
}
