给定一个 � × � n×m 列的 01 01 矩阵(只包含数字 0 0 或 1 1 的矩阵) 再执行 � Q 次询问 每次询问给出一个 � A 行 � B 列的 01 01 矩阵 求该矩阵是否在原矩阵中出现过

解题思路：

暴力枚举

- 对于每个查询矩阵，遍历原矩阵的每个可能的起点，再以该起点为左上角，判断查询矩阵是否与原矩阵中的子矩阵相等。

时间复杂度：$O(QnmAB)$

哈希

- 对于每个查询矩阵和原矩阵的每个可能的起点，计算该子矩阵的哈希值，再比较两个哈希值是否相等。

时间复杂度：$O(Qnm+nmAB)$

KMP

- 对于每个询问矩阵，将其转换为字符串。
- 对于原矩阵的每一行，将其转换为字符串，使用 KMP 算法在其中匹配询问矩阵转换后的字符串。
- 对于原矩阵的每一列，将其转换为字符串，使用 KMP 算法在其中匹配询问矩阵转换后的字符串。

时间复杂度：$O(Q(n+m)(nm+AB))$

AC 自动机

- 对于每个询问矩阵，将其转换为字符串。
- 将所有行和列转换为字符串，构建 AC 自动机。
- 在 AC 自动机上匹配询问矩阵转换后的字符串。

时间复杂度：$O(Q(AB+(n+m)(nm+AB)))$

代码实现：

暴力枚举

时间复杂度：$O(QnmAB)$

空间复杂度：$O(nm)$

C++ 代码

相关问题

给定一个 � × � n×m 的矩阵，如果一个元素为​ 0 0，则将其所在行和列的所有元素都改为 0 0 输入格式 输入第一行为两个不超过1000的正整数 � n 和 � m 接下来 � n 行每行 � m 个绝对值不超过1000的整数 c++

要实现给定一个 n×m 的矩阵，将元素为 0 的所在行和列的所有元素都改为 0，可以按照以下步骤进行操作：

1. 创建一个大小为 n×m 的二维数组 matrix，用于存储输入的矩阵。
2. 遍历矩阵，找到元素为 0 的位置。可以使用两个嵌套的循环来遍历矩阵的每个元素。
3. 当找到元素为 0 的位置时，将该元素所在行和列的所有元素都设置为 0。可以使用两个额外的数组来记录需要设置为 0 的行和列。
4. 再次遍历矩阵，根据记录的需要设置为 0 的行和列，将对应位置的元素设置为 0。

下面是一个示例的 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix.size();
    
    vector<int> zeroRows(rows, 0);
    vector<int> zeroCols(cols, 0);
    
    // 找到元素为 0 的位置
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0) {
                zeroRows[i] = 1;
                zeroCols[j] = 1;
            }
        }
    }
    
    // 设置对应位置的元素为 0
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (zeroRows[i] == 1 || zeroCols[j] == 1) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> matrix(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    
    setZeroes(matrix);
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

描述 给定一个m行n列的矩阵，现在要求让第a行第b列的数字与第c行第d列的数字互换位置，输出换过位置之后的矩阵。 （矩阵：由 m × n 个数排成的m行n列的数表称为m行n列的矩阵，简称m × n矩阵） 1 < = � , � < = 100 ， 1 < = � , � , � , � < = � � � ( � , � ) 1<=m,n<=100，1<=a,b,c,d<=min(m,n) 输入 第一行：六个整数，分别为m，n，a，b，c，d 接下来输入一个m行n列的矩阵 输出 输出交换后的矩阵 输入样例 1 5 4 3 3 1 4 1 2 3 4 4 3 2 1 6 7 8 9 9 8 7 6 4 5 6 7 输出样例1 1 2 3 8 4 3 2 1 6 7 4 9 9 8 7 6 4 5 6 7 提示 【样例解释】 a b c d分别为3 3 1 4 c++代码

#include<iostream>
using namespace std;
int main(){
    int m,n,a,b,c,d;
    cin>>m>>n>>a>>b>>c>>d;
    int a1[m+1][n+1];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a1[i][j];
        }
    }
    int temp=a1[a][b];
    a1[a][b]=a1[c][d];
    a1[c][d]=temp;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cout<<a1[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}