当前位置: 首页 > news >正文

字符串_哈希

 参考文章:

E. Compress Words(字符串hash)_z听歌的小孩z的博客-CSDN博客

字符串哈希 - OI Wiki (oi-wiki.org)

板子:

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+50;
typedef long long ll;
const int mod=1e9+7;
typedef unsigned long long ull;
char s[N];
int n;
ll h[N],p[N],base=31;
void init(){p[0]=1;for(int i=1;i<=n;i++){h[i]=(h[i-1]*base%mod+s[i])%mod;p[i]=p[i-1]*base%mod;}
}
int get_v(int l,int r){return ((h[r]-h[l-1]*p[r-l+1]%mod)%mod+mod)%mod;
}int main(){scanf("%s",s+1);n=strlen(s+1);init();return 0;
}
/*
ll p[3][N],h[3][N];
ll mod[3]={100000007,998244353,100000009},base[3]={73,87,61};
*/

例题: 

例1:2021_ICPC_山东 F- Birthday Cake - Codeforces(双哈希)

题解: 

看一个字符串的前缀和后缀,如果这两个前后缀相等,就去查询这个字符串除去这个前后缀之后还剩下的部分是否出现过,然后统计出现次数的答案 ps 我们把所有串按照串的长度从小到大排个序,一定要排,不然aaaa,aa这个数据就可以卡掉。 

/*eg:abcabcd    l=7 j=3 r=l-j+1=5 前缀[1,3] 后缀[5,7]chk(1,3)==chk(5,7)chk(4,6)
*/
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
typedef pair<ll,ll> pi;
const ll mod1=1e9+7,mod2=1e9+9;string s[N];
char ss[N];
int n;
ll res;
bool cmp(string x,string y){return x.length()<y.length();
}
ll p1[N],p2[N],h1[N],h2[N],P=31;
void init(){p1[0]=p2[0]=1;for(int i=1;i<N;i++)p1[i]=p1[i-1]*P%mod1,p2[i]=p2[i-1]*P%mod2;
}void get_h(int n){for(int i=1;i<=n;i++){h1[i]=(h1[i-1]*P%mod1+ss[i])%mod1;h2[i]=(h2[i-1]*P%mod2+ss[i])%mod2;}
}
ll getv1(int l,int r){return (h1[r]-h1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;
}
ll getv2(int l,int r){return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}
map<pi,int>mp;
int main(){init();scanf("%d",&n);for(int i=1;i<=n;i++)cin>>s[i];sort(s+1,s+1+n,cmp);for(int i=1;i<=n;i++){int len=s[i].length();for(int j=0;j<len;j++)ss[j+1]=s[i][j];get_h(len);//前缀==后缀for(int j=1;j<len-j+1;j++){//[1,j][r,len]int r=len-j+1;if(getv1(1,j)==getv1(r,len)&&getv2(1,j)==getv2(r,len)){//除去前后缀的部分 [j+1,r-1]res+=mp[{getv1(j+1,r-1),getv2(j+1,r-1)}];}}ll v1=getv1(1,len),v2=getv2(1,len);//printf("end");//printf("i:%d [1,%d] [%d,%d] res%d\n",i,j,r,len,res);//printf("v1 %lld v2 %lld\n",v1,v2);res+=mp[{v1,v2}];mp[{v1,v2}]++;//printf("i:%d [1,%d] [%d,%d] res%d\n",i,j,r,len,res);}printf("%lld",res);return 0;
}

例2:E - Compress Words- Codeforces(双哈希)

题解:从长到短枚举每一个单词的前缀,和前面的所有单词匹配

*单哈希会被卡

*必须和前面所有单词匹配,不能只和前一个单词匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pi;
const ll mod[2]={100000007,100000009};int n,cnt;
char s[N],ss[N];ll h1[3][N],h2[3][N],p[3][N],P[3]={73,87,61};
int l1,l2;
inline void init(){p[0][0]=p[1][0]=p[2][0]=1;for(int k=0;k<2;k++)for(int i=1;i<N;i++)p[k][i]=(p[k][i-1]*P[k])%mod[k];
}
inline void geth(int n,int num){for(int j=0;j<num;j++)for(int i=1;i<=n;i++)h1[j][i]=((h1[j][i-1]*P[j])%mod[j]+s[i])%mod[j];
}inline ll getv2(int l,int r,int i){return ((h2[i][r]-(h2[i][l-1]*p[i][r-l+1])%mod[i])%mod[i]+mod[i])%mod[i];
}
int main(){init();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);l1=strlen(s+1);//printf("i%d %s l1:%d\n",i,s+1,l1);geth(l1,2);int anj=1;//printf("l2:%d l1:%d l2-l1+1:%d\n",l2,l1,l2-l1+1);int j1=l1,j2=l2-l1+1;if(j2<1)j1+=j2-1,j2=1;for(;j1>0&&j2<=l2;j1--,j2++){//printf("[1,%d]%lld [%d,%d]%lld %lld %lld %lld %lld\n",j1,h1[0][j1],j2,l2,getv2(j2,l2,0),h1[1][j1],getv2(j2,l2,1),h1[2][j1],getv2(j2,l2,2));if(h1[0][j1]==getv2(j2,l2,0)&&h1[1][j1]==getv2(j2,l2,1)){anj=j1+1;//printf("anj %d\n",anj);break;}}int t=cnt;for(int j=anj;j<=l1;j++)ss[++cnt]=s[j];//printf("cnt%d %s\n",cnt,ss+1);for(int j=0;j<2;j++)for(int i=t;i<=cnt;i++)h2[j][i]=((h2[j][i-1]*P[j])%mod[j]+ss[i])%mod[j];l2=cnt;}printf("%s",ss+1);return 0;
}

相关文章:

字符串_哈希

参考文章&#xff1a; E. Compress Words(字符串hash)_z听歌的小孩z的博客-CSDN博客 字符串哈希 - OI Wiki (oi-wiki.org) 板子&#xff1a; #include<bits/stdc.h> using namespace std; const int N2e450; typedef long long ll; const int mod1e97; typedef unsig…...

python 之enumerate()函数

文章目录 enumerate() 是 Python 中的一个内置函数&#xff0c;它用于在遍历可迭代对象&#xff08;如列表、元组、字符串等&#xff09;时同时获取每个元素的索引和值。这个函数非常有用&#xff0c;因为它允许您在迭代过程中轻松地访问元素的索引&#xff0c;而不需要手动维护…...

【LeetCode刷题(数据结构与算法)】:用队列实现栈

请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09; 实现 MyStack 类&#xff1a; void push(int x) 将元素 x 压入栈顶 int pop() 移除并返回栈顶元素 int top() 返…...

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递的方式的区别

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递方式的主要区别如下&#xff1a; 数据的流动方向&#xff1a; 在“客户端到服务器的数据传递”中&#xff0c;数据是从客户端&#xff08;如浏览器&#xff09;流向服务器。在“服务器上的数据传递”中&…...

LCR 181 字符串中的单词反转

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;LCR 181. 字符串中的单词反转 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 倒叙遍历&#xff0c;获得每个单词的起始位置与终止位置&#xff0c;然后将每次遇到的单词插入结果中。 解题…...

百度OCR识别图片文本字符串——物联网上位机软件

一、开发背景 根据项目需求&#xff0c;我们需要完成LED显示屏实时显示歌词的效果。最优的方法是调用歌曲播放器的API获取歌词&#xff0c;但是由于这个开发资格不是很好申请&#xff0c;因此我们采用其他方案&#xff0c;即通过OCR识别获取歌词&#xff0c;并投射到LED显示屏上…...

JAVA学习(6)-全网最详细~

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

睿趣科技:未来抖音开网店还有前景吗

随着科技的快速发展&#xff0c;电商平台已经成为了人们生活中不可或缺的一部分。在中国&#xff0c;抖音作为一个短视频平台&#xff0c;近年来迅速崛起&#xff0c;吸引了大量的用户和商家。那么&#xff0c;在未来&#xff0c;抖音是否还能为商家提供一个有效的电商平台呢?…...

第六章 应用层 | 计算机网络(谢希仁 第八版)

文章目录 第六章 应用层6.1 域名系统DNS6.1.1 域名系统概述6.1.2 互联网的域名结构6.1.3 域名服务器 6.2 文件传送协议6.2.1 FTP概述6.2.2 FTP的基本工作原理6.2.3 简单文件传送协议TFTP 6.3 远程终端协议TELNET6.4 万维网www6.4.1 万维网概述6.4.2 统一资源定位符URL6.4.3 超文…...

c++ lambda 表达式

1. 简介 lambda&#xff08;匿名函数&#xff09;是C11引入的一种函数对象&#xff0c;它允许我们在需要函数的地方创建一个临时的、匿名的函数。lambda表达式表示一个可以执行的代码单元&#xff0c;可以理解为一个未命名的内联函数。Lambda函数可以用于简化代码、提高可读性…...

Go语言入门心法(七): 并发与通道

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言并发与通道...

前端组件封装:构建模块化、可维护和可重用的前端应用

前端组件封装&#xff1a;构建模块化、可维护和可重用的前端应用 前端开发领域的快速演进已经将前端应用的规模和复杂性提升到了一个新的水平。在这个背景下&#xff0c;前端组件封装成为了一项关键实践&#xff0c;旨在构建模块化、可维护和可重用的前端应用。在本文中&#…...

GPT绘制流程图咒语

【咒语】下面是我的一篇论文选取部分&#xff0c;为了让读者更好理解&#xff0c;我准备画一张图&#xff0c;请你阅读后为我设计一下这个图应该怎么画&#xff0c;更有说服力&#xff0c;更容易理解 论文片段&#xff1a; 多模态数据融合研究的基础在于有效的数据采集。首先&a…...

【扩散模型从原理到实战】Chapter1 扩散模型简介

文章目录 1.1 扩散模型的原理生成模型扩散过程DDPM的扩散过程前向过程反向过程优化目标 1.2 扩散模型的发展开始扩散&#xff1a;DDPM加速生成&#xff1a;采样器刷新记录&#xff1a;基于CLIP的多模态图像生成引爆网络&#xff1a;基于CLIP的多模态图像生成再次“出圈”&#…...

使用轮廓分数提升时间序列聚类的表现

我们将使用轮廓分数和一些距离指标来执行时间序列聚类实验&#xff0c;并且进行可视化 让我们看看下面的时间序列: 如果沿着y轴移动序列添加随机噪声&#xff0c;并随机化这些序列&#xff0c;那么它们几乎无法分辨&#xff0c;如下图所示-现在很难将时间序列列分组为簇: 上面…...

蔬菜水果生鲜配送团购商城小程序的作用是什么

蔬菜水果是人们生活所需品&#xff0c;从业者众多&#xff0c;无论小摊贩还是超市商场都有不少人每天光临&#xff0c;当然这些只是自然流量&#xff0c;在实际经营中&#xff0c;蔬菜水果商家还是面临着一些难题。 对蔬菜水果商家而言&#xff0c;线下门店是重要的&#xff0…...

金融用户实践|分布式存储支持数据仓库业务系统性能验证

作者&#xff1a;深耕行业的 SmartX 金融团队 闫海涛 估值是指对资产或负债的价值进行评估的过程&#xff0c;这对于投资决策具有重要意义。每个金融公司资管业务人员都期望能够实现实时的业务估值&#xff0c;快速获取最新的数据和指标&#xff0c;从而做出更明智的投资决策。…...

代码随想录二刷 Day41

509. 斐波那契数 这个题简单入门&#xff0c;注意下N小于等于1的情况就可以 class Solution { public:int fib(int n) {if (n < 1) return n; //这句不写的话test能过但是另外的过不了vector<int> result(n 1); //定义存放dp结果的数组&#xff0c;还要定义大小r…...

C++项目实战——基于多设计模式下的同步异步日志系统-⑪-日志器管理类与全局建造者类设计(单例模式)

文章目录 专栏导读日志器建造者类完善单例日志器管理类设计思想单例日志器管理类设计全局建造者类设计日志器类、建造者类整理日志器管理类测试 专栏导读 &#x1f338;作者简介&#xff1a;花想云 &#xff0c;在读本科生一枚&#xff0c;C/C领域新星创作者&#xff0c;新星计…...

Hadoop3教程(十四):MapReduce中的排序

文章目录 &#xff08;99&#xff09;WritableComparable排序什么是排序什么时候需要排序排序有哪些分类如何实现自定义排序 &#xff08;100&#xff09;全排序案例案例需求思路分析实际代码 &#xff08;101&#xff09;二次排序案例&#xff08;102&#xff09; 区内排序案例…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...