首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。