字符匹配

题目描述

##算法设计
算法关键:

遍历子数组左上角

i从0到n-b+1,j从0到m-a+1

遍历这个子数组，不相同ret就设为0；

输入处理

扫描n,m,a,b

A[n][m]存原矩阵

扫描q

q次循环

B[a][b]存子矩阵

调用算法

将结果存在ans数组中

代码很简单

    int n, m, a, b;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    char A[n][m];
    char B[a][b];
    for (int i = 0; i < n; ++i) {
        scanf("%s",A[i]);
    }
    int q;
    scanf("%d", &q);
    int ans[q];
    int valEn = 0;
    for (int i = 0; i < q; ++i) {
        //存B
        for (int j = 0; j < a; ++j) {
            scanf("%s",B[j]);
        }

运算

按照算法写出代码

    int n, m, a, b;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    char A[n][m];
    char B[a][b];
    for (int i = 0; i < n; ++i) {
        scanf("%s",A[i]);
    }
    int q;
    scanf("%d", &q);
    int ans[q];
    int valEn = 0;
    for (int i = 0; i < q; ++i) {
        //存B
        for (int j = 0; j < a; ++j) {
            scanf("%s",B[j]);
        }

测试运行

矩阵是char类型的，加上一些对缓冲区的修改

加入调试语句输出A、B

#ifdef DEBUG
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < n; ++k) {
                printf("%c ", A[j][k]);
            }
            printf("\n");
        }
        printf("\n");
        for (int j = 0; j < a; ++j) {
            for (int k = 0; k < b; ++k) {
                printf("%c ", A[j][k]);
            }
            printf("\n");
        }
#endif

输入正常了

测试

发现是比较时对B的调用有问题，改为列指针调用B

删除标志变量，改用更简洁的goto：但凡不相等，就到结束标记点

    int ans[q];
    int valEn = 0;
    for (int i = 0; i < q; ++i) {
        //存B
        for (int j = 0; j < a; ++j) {
            scanf("%s", B[j]);
        }
        //解决
        int count = 0;
        for (int j = 0; j < n - b + 1; ++j) {
            for (int k = 0; k < m - a + 1; ++k) {//a[j][k]是子数组左上角元素
                int num = 0;
                char *p = B[0];
                for (int hang = j; hang < j + a; ++hang) {
                    for (int lie = k; lie < k + b; ++lie) {
                        if (A[hang][lie] != p[num++]) {
                            goto end;
                        }
                    }
                }
                count++;
                end:;
            }
        }
        ans[valEn++] = count;
    }