题意就是一个给出2个字符矩阵,然后进行匹配,输出每个位置的匹配的结果
(超出的部分循环处理)
一种做法是使用fft,比较难写,所以没有写
这里使用一个暴力的做法,考虑到一共只出现26个字符
所以使用一个数组G[c][i][j]表示字符c是否出现在位置(i, j),即G[c]是一个01矩阵
可以使用bitset定义G
然后考虑匹配的时候
考虑要匹配的那个矩阵B,如果当前字符是?就跳过
如果不是,就考虑这个字符会对哪些匹配位置造成影响
用bitset表示一行的状态,然后使用and和左移、右移就可以更新答案矩阵
复杂度是O(n*m*r*c/32) (bitset优化)
#include <iostream> #include <cstdio> #include <bitset> using namespace std; const int N = 404; char str[500]; bitset<N> G[27][N], A[N]; int n, m, r, c; bitset<N> shift(char c, int i, int x) { bitset<N> temp = G[c][i]; return (temp>>x)|(temp<<(m-x)); } int main() { //freopen("a.txt", "r", stdin); scanf("%d %d", &n, &m); for(int i = 0; i < n; i ++) { scanf("%s", str); for(int j = 0; j < m; j++) G[str[j]-'a'][i][j] = 1, A[i][j] = 1; } scanf("%d %d", &r, &c); for(int i = 0; i < r; i++) { scanf("%s", str); for(int j = 0; j < c; j++) { char ch = str[j]; if(ch == '?') continue; for(int k = 0; k < n; k++) A[k] = (A[k] & shift(ch-'a', (k+i)%n, j%m)); } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) printf("%d", A[i][j] ? 1 : 0); printf(" "); } }