http://fastvj.rainng.com/problem/UVA-11019
题意很简单不说了；
做法：首先考虑一维字符串如何哈希公式如下：
然后类比得到二维字符串的哈希公式
其他都还差不多的。
时间复杂度不是n*m
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll hs1=200379; const ll hs2=196613; const ll mod=1e9+7; const int N=1010; const int M=110; ll p1[N],p2[N]; ll hs[N][N]; int m,n,x,y; char s[N][N],t[N][N]; void init() { p1[0]=p2[0]=1; for(int i=1;i<N;i++) p1[i]=p1[i-1]*hs1%mod; for(int i=1;i<N;i++) p2[i]=p2[i-1]*hs2%mod; } int main() { init(); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); scanf("%d%d",&x,&y); for(int i=1;i<=x;i++) scanf("%s",t[i]+1); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { hs[i][j]=hs[i-1][j]*hs1%mod+hs[i][j-1]*hs2%mod-hs[i-1][j-1]*hs1%mod*hs2%mod+s[i][j]; hs[i][j]=(hs[i][j]+mod)%mod; } } ll cnt=0,tmp=0; int ans=0; for(int i=1;i<=x;i++) { for(int j=1;j<=y;j++) { cnt=(cnt+t[i][j]*p1[x-i]%mod*p2[y-j]%mod)%mod; } } for(int i=x;i<=n;i++) { for(int j=y;j<=m;j++) { tmp=((hs[i][j]-hs[i-x][j]*p1[x]%mod+mod)%mod-hs[i][j-y]*p2[y]%mod+mod)%mod+hs[i-x][j-y]*p1[x]%mod*p2[y]%mod; tmp%=mod; if(tmp==cnt) ans++; } } printf("%d\n",ans); } return 0; }AC自动机
这个AC自动机就不怎么好想了，而且效率也不高
方法是利用count[i][j]来记录以(i,j)为左上角，且大小为X，Y的矩形中含有多少个完整行与第二个矩阵对应行完全相同。 所以，如果在第一个矩阵的第r行的第c列开始与第二个的第i行匹配，那么count[r-i][c]++; 最后判断是否有count[][]==X;
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=300+10; const int MAXN=100010; const int M=1010; struct node { int next[MAXN][N]; int fail[MAXN]; int endd[MAXN]; int last[MAXN]; int vt[MAXN][N]; int vn[MAXN]; int cnt[M][M]; int root,l; int newnode() { memset(next[l],0,sizeof(next[l])); endd[l]=fail[l]=last[l]=vn[l]=0; return l++; } void init() { memset(cnt,0,sizeof(cnt)); l=0; root=newnode(); } void Insert(char *s,int id) { int len=strlen(s); int now=root; for(int i=0;i<len;i++) { if(next[now][s[i]]==0) next[now][s[i]]=newnode(); now=next[now][s[i]]; } endd[now]=1; vt[now][vn[now]++]=id; } void build() { queue<int>qu; int now=root; for(int i=0;i<N;i++) { if(next[root][i]) qu.push(next[root][i]); } while(!qu.empty()) { now=qu.front(); qu.pop(); for(int i=0;i<N;i++) { int v=next[now][i]; if(v) { fail[v]=next[fail[now]][i]; last[v]=(endd[fail[v]]?fail[v]:last[fail[v]]); qu.push(v); } else next[now][i]=next[fail[now]][i]; } } } void print(int r,int c,int j) { if(j) { for(int i=0;i<vn[j];i++) if(r>=vt[j][i]) cnt[r-vt[j][i]][c]++; print(r,c,last[j]); } } void ffind(int r,char *s) { int now=root; int len=strlen(s); for(int i=0;i<len;i++) { int v=s[i]; now=next[now][v]; if(endd[now]) print(r,i,now); else if(last[now]) print(r,i,last[now]); } } }; node Aho; char str[M][M],tt[M][M]; int n,m,x,y; int main() { int T;scanf("%d",&T); while(T--) { Aho.init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",str[i]); scanf("%d%d",&x,&y); for(int i=1;i<=x;i++) { scanf("%s",tt[i]); Aho.Insert(tt[i],i); } int ans=0; Aho.build(); for(int i=1;i<=n;i++) { Aho.ffind(i,str[i]); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(Aho.cnt[i][j]==x) ans++; } } printf("%d\n",ans); } return 0; }
