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

字符串hash

K - 子串翻转回文串

2020ccpc河南省赛

字符串哈希:将字符串变成x进制数

对公式的理解:

举个十进制数的例子:123456

h[1]=1;

h[2]=1*10+2=12;

h[3]=12*10+3=123;

h[4]=123*10+4=1234;

.........

h[i]=h[i-1]*x+a[i];

h[i]代表的恰巧是整个数的前缀

用p[i]表示进制数的 i 次方;

想要单取出3-5的子串的值345

步骤;

1,先取出前缀12345(q[5])

2,再减去12000:(h[2]*1000);

取子串哈希值的公式为:h[r]-h[l-1] *(r-l+1);

本题思路:

去掉前缀后缀相同的部分,剩余的前缀或后缀必定要翻转一次

判法:正反跑一次哈希(下标不变权值翻转)

--------------------------------------> 正向权值整串s1

----------> 正向权值翻转部分s2

<---------- 反向权值翻转部分s3

<-------------------------------------- 正向权值整串s4

判法:比较翻转前与翻转后的整串的哈希制是否一样

long long get1(int l,int r)

{

if(l==0) return h1[r];

return ((h1[r]%mod-h1[l-1]*p[r-l+1]%mod)+mod)%mod;/*注意负数取模*/

}

求正向的字符串的hash值

long long get2(int l,int r)

{

return (h2[l]%mod-h2[r+1]*p[r-l+1]%mod+mod)%mod;

}

求反向的字符串的hash值

反向之后如12345中的5是最高位,如求1-3的话我们就应该让a[1]-a[4]*10的(r-l+1)次方

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int N = 5e5+10;
int st[N];int ed[N];int p[N];
int base=131;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int get1(int l,int r)
{return (st[r]-st[l-1]*p[r-l+1]%mod+mod)%mod;
}
int get2(int l,int r)
{return (ed[l]-ed[r+1]*p[r-l+1]%mod+mod)%mod;
}
bool check(int l,int r,int len)
{int dex = (st[len] - get1(l, r) * p[len - r] % mod + get2(l, r) * p[len - r] % mod + mod) % mod;/*从s1中取出s2放入s3所得出整串的哈希值*/int dey = (ed[1] - get2(l, r) * p[l - 1] % mod + get1(l, r) * p[l - 1] % mod + mod) % mod;/*从s4中取出s3放入s2所得出整串的哈希值*/    return dex == dey;
}
void solve()
{string s;cin>>s;int len=s.size();s=" "+s;int f=1;for(int i=1;i<=len/2;i++){if(s[i]!=s[len-i+1]){f=0;break;}} if(f==1){cout<<"Yes"<<endl;return ;}else{int pos;for(int i=1;i<=len;i++){if(s[i]!=s[len-i+1]){pos=i;break;}}p[0]=1;for(int i=1;i<=len;i++){st[i]=(st[i-1]*base%mod+s[i])%mod;    p[i]=p[i-1]*base%mod;}ed[len+1]=0;for(int j=len;j>=1;j--){ed[j]=(ed[j+1]*base%mod+s[j])%mod;}for(int i=pos;i<=len-pos+1;i++){int l=pos,r=i;int ll=i,rr=len-pos+1;if(check(l,r,len)||check(ll,rr,len)){cout<<"Yes"<<endl;return ;}    }    }cout<<"No"<<endl;
}
signed main()
{ios;int t;cin>>t;while(t--){solve();}
}

相关文章:

字符串hash

K - 子串翻转回文串2020ccpc河南省赛字符串哈希&#xff1a;将字符串变成x进制数对公式的理解&#xff1a;举个十进制数的例子&#xff1a;123456h[1]1&#xff1b;h[2]1*10212;h[3]12*103123;h[4]123*1041234;.........h[i]h[i-1]*xa[i];h[i]代表的恰巧是整个数的前缀用p[i]表…...

试题 算法训练 转圈游戏

问题描述 n个小伙伴&#xff08;编号从0到n-1&#xff09;围坐一圈玩游戏。按照顺时针方向给n个位置编号&#xff0c;从0到n-1。   最初&#xff0c;第0号小伙伴在第0号位置&#xff0c;第1号小伙伴在第 1 号位置&#xff0c;……&#xff0c;依此类推。   游戏规则如下&am…...

【uni-app教程】九、运行环境判断与跨端兼容

&#xff08;1&#xff09;开发环境和生产环境 uni-app 可通过 process.env.NODE_ENV 判断当前环境是开发环境还是生产环境&#xff0c;一般用于连接测试服务器或生产服务器的动态切换。 在HBuilderX 中&#xff0c;点击「运行」编译出来的代码是开发环境&#xff0c;点击「发行…...

扩展WSL2虚拟硬盘的大小

扩展WSL2虚拟硬盘的大小 1、在 Windows PowerShell 中终止所有 WSL 实例 wsl --shutdown2、查看 WSL 实例运行状态&#xff0c;确认关闭&#xff0c;并记住发行版的名称 wsl -l -v如果没有更改移动过发行版安装包位置&#xff0c;那么可以通过以下方法查找到发行版的安装包位…...

Win系统蓝牙设备频繁卡顿/断连 - 解决方案

Win系统蓝牙设备频繁卡顿/断连 - 解决方案前言常见网卡Intel无线网卡&#xff08;推荐&#xff09;Realtek无线网卡总结查看本机网卡解决方案更新驱动更换网卡&#xff08;推荐&#xff09;前言 无线网卡有2个模块&#xff0c;一个是WiFi&#xff0c;一个是蓝牙&#xff0c;因…...

Git学习入门(2)- 基本命令操作总结

个人博客&#xff1a;我的个人博客&#xff0c;各位大佬来玩1 创建 git仓库1.1 从现有工作目录中初始化新仓库需要到你需要用git管理的项目中输入以下命令&#xff1a;git init便会创建一个空的git项目&#xff0c;并且当前目录下会出现一个名为 .git 的目录&#xff0c; Git 需…...

SPringCloud:Nacos快速入门及相关属性配置

目录 一、Nacos快速入门 1、在父工程中添加spring-cloud-alilbaba的管理依赖 2、如果有使用eureka依赖&#xff0c;将其注释 3、添加nacos的客户端依赖 4、修改yml文件&#xff0c;注释eureka配置 5、启动测试 二、Nacos相关属性配置 1、Nacos服务分级存储 2、根据集群…...

医疗器械之模糊算法(嵌入式部分)

模糊控制 所谓模糊控制&#xff0c;就是对难以用已有规律描述的复杂系统&#xff0c;采用自然语言&#xff08;如大&#xff0c;中&#xff0c;小&#xff09;加以描述&#xff0c;借助定性的&#xff0c;不精确的以及模糊的条件语句来表达&#xff0c;模糊控制是一种基于语言的…...

网上销售笔记本系统

技术&#xff1a;Java、JSP等摘要&#xff1a;本文讲述了基于B/S模式的笔记本电脑在线销售系统的设计与实现。所谓的笔记本电脑在线销售系统是通过网站推广互联企业的笔记本电脑和技术服务&#xff0c;并使客户随时可以了解企业和企业的产品&#xff0c;为客户提供在线服务和订…...

MySQL基础查询操作

文章目录&#x1f68f; Select语句&#x1f680; 一、SQL底层执行原理&#x1f6ac; &#xff08;一&#xff09;、查询的结构&#x1f6ac; &#xff08;二&#xff09;、SQL语句的执行过程&#x1f6ad; 1、WHERE 为什么不包含聚合函数的过滤条件&#xff1f;&#xff08;面试…...

English Learning - L2 语音作业打卡 小元音 [ʌ] [ɒ] Day9 2023.3.1 周三

English Learning - L2 语音作业打卡 小元音 [ʌ] [ɒ] Day9 2023.3.1 周三&#x1f48c;发音小贴士&#xff1a;&#x1f48c;当日目标音发音规则/技巧:&#x1f36d; Part 1【热身练习】&#x1f36d; Part2【练习内容】&#x1f36d;【练习感受】&#x1f353;元音 [ʌ]&…...

Condition 源码解读

一、Condition 在并发情况下进行线程间的协调&#xff0c;如果是使用的 synchronized 锁&#xff0c;我们可以使用 wait/notify 进行唤醒&#xff0c;如果是使用的 Lock 锁的方式&#xff0c;则可以使用 Condition 进行针对性的阻塞和唤醒&#xff0c;相较于 wait/notify 使用…...

看完这篇入门性能测试

大家好&#xff0c;我是洋子。最近组内在进行服务端高并发接口的性能压测工作&#xff0c;起因是2023年2月2日&#xff0c;针对胡某宇事件进行新闻发布会直播&#xff0c;几十万人同时进入某媒体直播间&#xff0c;造成流量激增 从监控上可以看出&#xff0c;QPS到达某峰值后&…...

推导部分和——带权并查集

题解&#xff1a; 带权并查集 引言&#xff1a; 带权并查集是一种进阶的并查集&#xff0c;通常&#xff0c;结点i的权值等于结点i到根节点的距离&#xff0c;对于带权并查集&#xff0c;有两种操作需要掌握——Merge与Find&#xff0c;涉及到路径压缩与维护权值等技巧。 带…...

费解的开关/翻硬币

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a; 算法 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 题目&#xff1a;费解的开关 你玩过“拉灯”游戏吗&#xff1f; 25盏灯排成一个 55 的方形。 每一个灯都有一个开关&…...

OpenGL中的坐标系

1、2D笛卡尔坐标系2D笛卡尔坐标系跟我们高中的时候学习的坐标系一样&#xff0c;是由x、y决定的。2、3D笛卡尔坐标系3D笛卡尔坐标系坐标由x、y、z决定&#xff0c;满足右手定则。3、视口glViewport(GLint x,GLint y,GLsizei width,GLsizei height)窗口和视口大小可以相同&#…...

Spring——Spring介绍和IOC相关概念

Spring是以Spring Framework为核心&#xff0c;其余的例如Spring MVC&#xff0c; Spring Cloud&#xff0c;Spring Data&#xff0c;Spring Security SpringBoot的基础都是Spring Framework。 Spring Boot可以在简化开发的基础上加速开发。 Spring Cloud分布式开发 Spring有…...

A+B Problem

AB Problem 题目描述 输入两个整数 a,ba, ba,b&#xff0c;输出它们的和&#xff08;∣a∣,∣b∣≤109|a|,|b| \le {10}^9∣a∣,∣b∣≤109&#xff09;。 注意 Pascal 使用 integer 会爆掉哦&#xff01;有负数哦&#xff01;C/C 的 main 函数必须是 int 类型&#xff0c;…...

【ROS学习笔记11】ROS元功能包与launch文件的使用

【ROS学习笔记11】ROS元功能包与launch文件的使用 文章目录【ROS学习笔记11】ROS元功能包与launch文件的使用前言一、ROS元功能包二、ROS节点运行管理launch文件2.1 launch文件标签之launch2.2 launch文件标签之node2.3 launch文件标签之include2.4 launch文件标签之remap2.5 l…...

【python】

print函数 同时输出多行变量 print(a, b, sep\n) (23条消息) python3 中print函数参数详解&#xff0c;print(*values, sep , end\n, filesys.stdout, flushFalse)中参数介绍_sep,_phantom-dapeng的博客-CSDN博客 input() 输入浮点数&#xff0c;不能用int(input()) int()…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...