1 条题解

  • 1
    @ 2022-5-7 17:31:09

    题意:给定 n×mn \times mm×nm \times n 的两个小写字符矩阵 sstt ,要求找出它们任意一个相同的 m×mm \times m 的子矩阵,输出 ss 中开始的行和 tt 中开始的列。

    先枚举一下这个子矩阵在 tt 中是从那一列开始的,这样就确定了这个子矩阵。现在我们尝试在一个 n×mn \times m 的矩阵中匹配一个 m×mm\times m 的矩阵。列数都是 mm ,所以直接对于每行哈希然后 kmp\tt{kmp} 即可。

    复杂度 O(n2)O(n ^ 2)

    CODE
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    
    inline int read() {
    	int x = 0, f = 0; char c = 0;
    	while (!isdigit(c)) f |= c == '-', c = getchar();
    	while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    	return f ? -x : x;
    }
    
    #define N 2005
    #define B 1919
    #define P 998244353
    
    int n, m, pw[N], iv[N], a[N], b[N][N], c[N], nex[N];
    char s[N][N], t[N][N];
    
    int Pow(int x, int k, int r = 1) {
    	for (; k; k >>= 1, x = x * x % P) {
    		if (k & 1) r = r * x % P;
    	}
    	return r;
    }
    
    int geh(int i, int l, int r) {
    	return (b[i][r] - b[i][l - 1] + P) % P * iv[l - 1] % P;
    }
    
    signed main() {
    	pw[0] = iv[0] = 1;
    	for (int i = 1; i < N; i ++) {
    		pw[i] = pw[i - 1] * B % P;
    		iv[i] = Pow(pw[i], P - 2);
    	}
    
    	n = read(), m = read();
    	for (int i = 1; i <= n; i ++) scanf("%s", s[i] + 1);
    	for (int i = 1; i <= m; i ++) scanf("%s", t[i] + 1);
    
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= m; j ++) {
    			(a[i] += (s[i][j] & 31) * pw[j - 1]) %= P; 
    		}
    	}
    	for (int i = 1; i <= m; i ++) {
    		for (int j = 1; j <= n; j ++) {
    			b[i][j] = (b[i][j - 1] + (t[i][j] & 31) * pw[j - 1]) % P; 
    		}
    	}
    
    	for (int i = 2, j = 0; i <= n; i ++) {
    		while (j && a[i] != a[j + 1]) j = nex[j];
    		nex[i] = (j += (a[i] == a[j + 1]));
    	}
    
    	for (int k = 1; k + m - 1 <= n; k ++) {
    		for (int j = 1; j <= m; j ++) {
    			c[j] = geh(j, k, k + m - 1);
    		}
    		for (int i = 1, j = 0; i <= n; i ++) {
    			while (j && (a[i] != c[j + 1])) j = nex[j];
    			if (a[i] == c[j + 1]) j ++;
    			if (j == m) return printf("%lld %lld\n", i - m + 1, k), 0;
    		}
    	}
    	return 0;
    }
    

    打死也不告诉你可以暴力水过,都给我去码哈希kmp

    • 1

    信息

    ID
    2973
    时间
    2000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    2
    已通过
    1
    上传者