强烈建议你试试无所不能的chatGPT，快点击我

UVALive - 6893 The Big Painting 字符串哈希

阅读量：4346 次

发布时间：2019-06-07

本文共 1950 字，大约阅读时间需要 6 分钟。

题目链接：

The Big Painting

Time Limit: 5000MS

题意

给你一个模板串和待匹配串，问模板串在待匹配串中出现的次数（这里的串是二维矩阵）

题解

每一行做前缀和哈希。
统计的时候先按列再按行，这样在做行的话我们可以利用滚动的形式，计算纵向的哈希值（既总的哈希值）

代码

#include#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define X first#define Y second#define mkp make_pair#define lson (o<<1)#define rson ((o<<1)|1)#define mid (l+(r-l)/2)#define sz() size()#define pb(v) push_back(v)#define all(o) (o).begin(),(o).end()#define clr(a,v) memset(a,v,sizeof(a))#define bug(a) ;//cout<<#a<<" = "<
             <

VI;typedef pair

PII;typedef vector

> VPII;const int INF=0x3f3f3f3f;const LL INFL=0x3f3f3f3f3f3f3f3fLL;const double eps=1e-8;//start----------------------------------------------------------------------const int maxn=2020;//P进制哈希const int P=123;unsigned long long H[maxn][maxn],xp[maxn*maxn],Val;int n1,m1,n2,m2;char s1[maxn][maxn],s2[maxn][maxn];//预处理出位权void pre() { xp[0]=1; rep(i,1,maxn*maxn) xp[i]=xp[i-1]*P;}//处理前缀和的哈希值void get_H() { Val=0; rep(i,1,n1+1) rep(j,1,m1+1) { Val=Val*P+(s1[i][j]-'a'+1); } clr(H,0); rep(i,1,n2+1) rep(j,1,m2+1) { H[i][j]=H[i][j-1]*P+(s2[i][j]-'a'+1); }}//枚举，匹配void solve() { int ans=0; for(int j=1; j<=m2-m1+1; j++) { unsigned long long tmp=0,tmp2=0; int lj=j-1,rj=j+m1-1; int i; for(i=1;i<=n1;i++){ tmp=tmp*xp[m1]+H[i][rj]-H[i][lj]*xp[m1]; } do{ if(Val==tmp) ans++; tmp-=(H[i-n1][rj]-H[i-n1][lj]*xp[m1])*xp[m1*(n1-1)]; tmp=tmp*xp[m1]+H[i][rj]-H[i][lj]*xp[m1]; i++; }while(i<=n2+1); } printf("%d\n",ans);}int main() { pre(); while(scanf("%d%d%d%d",&n1,&m1,&n2,&m2)==4&&n1) { rep(i,1,n1+1) scanf("%s",s1[i]+1); rep(i,1,n2+1) scanf("%s",s2[i]+1); get_H(); solve(); } return 0;}//end-----------------------------------------------------------------------/*4 4 10 10oxxoxooxxooxoxxoxxxxxxoxxooxxoooxooxxooxxxxooxxooxxxoxxooxxoxxxxxxooooxxxxxxxxxoxxoxxooooxooxooxoooxooxooxxxxoxxoxxo*/

转载于:https://www.cnblogs.com/fenice/p/5774901.html

你可能感兴趣的文章

tomcat 7服务器跨域问题解决

前台实现ajax 需注意的地方

Jenkins安装配置

个人工作总结05（第二阶段）

深入理解Java虚拟机&运行时数据区

02-环境搭建

spring第二冲刺阶段第七天

搜索框键盘抬起事件2

阿里百川SDK初始化失败错误码是203

透析Java本质-谁创建了对象,this是什么

BFS和DFS的java实现

关于jquery中prev()和next()的用法

一、 kettle开发、上线常见问题以及防错规范步骤

eclipse没有server选项

CRC码计算及校验原理的最通俗诠释

使用Gitbook来编写你的Api文档

jquery扩展 $.fn

influxDB的安装和简单使用

JPA框架学习

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-10-07 19:30:00 当前IP: 3.143.235.23 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我