LA 6893 矩阵HASH (模板)

#include<stdio.h>
#include<string.h>
typedef unsigned long long ULL;
const ULL Base1 = ;
const ULL Base2 = ; int test,n,m,x,y;
ULL ans;
char s[][],a[][];
ULL hash;
ULL temp[][],Temp[][];
ULL Gethash()
{
ULL c,d = ;
for(int i = ; i < x; ++i) {
c = ;
for(int j = ; j < y; ++j)
{
c = c*Base1 + a[i][j];
}
d = d * Base2 + c;
}
return d;
} void GetAns() {//把矩阵中的hash算出来,每个子矩阵的。
ULL t,a; // 算的时候与目标hash匹配判断一下....
t = ;
for(int i = ; i < y; ++i) t *= Base1;
for(int i = ; i < n; ++i) {
a = ;
for(int j = ; j < y; ++j) a = a*Base1 + s[i][j];
temp[i][y-] = a;
for(int j = y; j < m; ++j) {
temp[i][j]=temp[i][j-]*Base1-s[i][j-y]*t+s[i][j];
}
} t = ;
for(int i = ; i < x; ++i) t *= Base2;
for(int i = y-; i < m; ++i) {
a = ;
for(int j = ; j < x; ++j) a = a*Base2 + temp[j][i];
Temp[x-][i] = a;
if(a == hash) ans++;
for(int j = x; j < n; ++j) {
Temp[j][i] = Temp[j-][i]*Base2 - temp[j-x][i] * t + temp[j][i];
if(Temp[j][i]== hash) ans++;
}
}
} int main()
{
while(scanf("%d%d%d%d",&x,&y,&n,&m)!= EOF) {
//scanf("%d%d",&n,&m);
for(int i = ; i < x; ++i) scanf("%s",a[i]);
//scanf("%d%d",&n,&m);
for(int i = ; i < n; ++i) scanf("%s",s[i]);
hash = Gethash();
ans = ;
GetAns();
printf("%llu\n",ans);
}
return ;
}
上一篇:sharepoint2010升级到sharepoint2013的升级步骤和过程


下一篇:ReactiveX 学习笔记(25)使用 RxJS + Vue.js 调用 REST API