文章目錄

• • 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?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;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)//記得寫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子串哈希值elsehash_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;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-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;}elsehash_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;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; }

總結

以上是生活随笔為你收集整理的POJ 3690 找星座（2D匹配）（未解答）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。