首页 > 代码库 > UVA - 11019 Matrix Matcher hash+KMP

UVA - 11019 Matrix Matcher hash+KMP

题目链接:https://vjudge.net/problem/UVA-11019

题解:

  赶着回寝室

  明天写题解

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 2e3+10, M = 1e3+20,inf = 2e9;const ULL mod = 10000019ULL;int n,m,x,y,T,fail[N];char a[N][N],b[N][N];ULL has[N][N],mp[N][N],s[N],t[N],sqr[N];void build_fail() {    int j = 0;    memset(fail,0,sizeof(fail));    for(int i = 2; i <= y; ++i) {        while(j&&s[i]!=s[j+1]) j = fail[j];        if(s[i] == s[j+1]) j++;        fail[i] = j;    }}int kmp() {    int ret = 0, j = 0;    for(int i = 1; i <= n; ++i) {        while(j&&s[j+1]!=t[i]) j = fail[j];        if(s[j+1] == t[i]) j++;        if(j == x) {            ret += 1;            j = fail[j];        }    }    return ret;}int main() {    sqr[0] = 1;    for(int i = 1; i < N; ++i) sqr[i] = sqr[i-1] * mod;    scanf("%d",&T);    while(T--) {        scanf("%d%d",&n,&m);        for(int i = 1; i <= n; ++i) scanf("%s",a[i]+1);        scanf("%d%d",&x,&y);        for(int i = 1; i <= x; ++i) scanf("%s",b[i]+1);        if(n < x || m < y) {            puts("0");            continue;        }        for(int i = 1; i <= n; ++i) {            for(int j = 1; j <= m; ++j)                has[i][j] = has[i][j - 1] * mod + a[i][j];        }        for(int i = 1; i <= x; ++i) {            ULL now = 0, ps = 1;            for(int j = 1; j <= y; ++j) {                now = now * mod + b[i][j];            }            s[i] = now;        }        build_fail();        int ans = 0;        for(int j = 1; j <= m - y + 1; ++j) {            for(int i = 1; i <= n; ++i) {                int l = j, r = j + y - 1;                ULL now = has[i][r] - has[i][l-1] * sqr[r - l + 1];                t[i] = now;            }            ans += kmp();        }        printf("%d\n",ans);    }    return 0;}

 

UVA - 11019 Matrix Matcher hash+KMP