题目分析
考虑将大矩阵的每个1*q矩阵哈希值求出，然后让小矩阵的第一行在大矩阵中找，如果找到，并且能匹配所有行则出现过。否则没出现过。
在初始化1*q矩阵时可以进行优化：假设该行为123456，要求1*5的矩阵哈希值，可以先暴力求出1~5，为 $1 * H^4 + 2 * H^3 + 3 * H^2 + 4 * H + 5$，现在要删除1添加6：变为$2 * H^4 + 3 * H^3 + 4 * H^2 + 5 * H + 6$，也就是先减去1的哈希值乘以$H^{len - 1}$，然后乘以H，加上6的哈希值。代码如下:
for(int i = 1; i <= n; i++){ for(int k = 1; k <= q; k++) fixedHash[i][1] = fixedHash[i][1] * H + getVal(matrix[i][k]); for(int j = 2; j <= m - q + 1; j++) fixedHash[i][j] = (fixedHash[i][j - 1] - getVal(matrix[i][j - 1]) * poww[q - 1]) * H + getVal(matrix[i][j + q - 1]); } code
#include#include #include #include #include #include using namespace std;const int N = 1005;typedef unsigned long long ull;const ull H = 2;ull fixedHash[N][N], hash[100], poww[100];int n, m, T, p, q, k;char matrix[N][N], small[100][100];inline int getVal(char x){ return x == '*' ? 1 : 0;}inline bool check(int x, int y){ for(int k = x + 1; k <= x + p - 1; k++) if(fixedHash[k][y] != hash[k - x + 1]) return false; return true;}int main(){ freopen("h.in", "r", stdin); poww[0] = 1; for(int i = 1; i <= 100; i++) poww[i] = poww[i - 1] * H; while(scanf("%d%d%d%d%d", &n, &m, &T, &p, &q), n + m + T + p + q){ memset(matrix, 0, sizeof matrix); for(int i = 1; i <= n; i++) scanf("%s", matrix[i] + 1); memset(fixedHash, 0, sizeof fixedHash); for(int i = 1; i <= n; i++){ for(int k = 1; k <= q; k++) fixedHash[i][1] = fixedHash[i][1] * H + getVal(matrix[i][k]); for(int j = 2; j <= m - q + 1; j++) fixedHash[i][j] = (fixedHash[i][j - 1] - getVal(matrix[i][j - 1]) * poww[q - 1]) * H + getVal(matrix[i][j + q - 1]); } int cnt = 0; for(int i = 1; i <= T; i++){ memset(small, 0, sizeof small); for(int j = 1; j <= p; j++) scanf("%s", small[j] + 1); memset(hash, 0, sizeof hash); for(int j = 1; j <= p; j++) for(int k = 1; k <= q; k++) hash[j] = hash[j] * H + getVal(small[j][k]); bool flag = true; for(int j = 1; j <= n - p + 1; j++){ for(int k = 1; k <= m - q + 1; k++){ if(fixedHash[j][k] == hash[1]) if(check(j, k)){ cnt++; flag = false; break; } } if(!flag) break; } } printf("Case %d: %d\n", ++k, cnt); }}