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

字符串哈希算法详解：原理、实现与应用

news 来源：原创 2025/9/21 11:56:43

字符串哈希是一种高效处理字符串匹配和比较的技术，它通过将字符串映射为一个唯一的数值（哈希值），从而在O(1)时间内完成子串的比较。本文将结合代码实现，详细讲解前缀哈希法的工作原理，并通过流程图逐步解析其执行过程。

. 字符串哈希的核心思想

字符串哈希的核心目标是：

将任意长度的字符串转换为固定大小的哈希值。
支持快速比较两个子串是否相同（时间复杂度O(1)）。
适用于大规模文本处理（如DNA序列比对、 plagiarism检测等）。

1.1 哈希函数设计

常用的字符串哈希方法是多项式滚动哈希（Polynomial Rolling Hash），其公式为：

H(S)=(S[0]×Pn−1+S[1]×Pn−2+⋯+S[n−1]×P0)mod MH(S)=(S[0]×Pn−1+S[1]×Pn−2+⋯+S[n−1]×P0)modM

其中：

PP 是一个质数（通常取131或13331）。
MM 是一个大数（如 264264，代码中用 unsigned long long 自然溢出替代取模）。

2. 代码实现解析

以下是基于前缀哈希的字符串匹配代码（支持快速比较任意两个子串）：

2.1 变量定义

#include <stdio.h>
#include <string.h>#define N 100010
#define P 131  // 经验值，减少冲突typedef unsigned long long Ull;Ull h[N];  // h[i]存储前i个字符的哈希值
Ull p[N];  // p[i]存储P的i次幂

2.2 初始化哈希数组

int main() {int n, m;char str[N];scanf("%d%d", &n, &m);scanf("%s", str + 1);  // 从str[1]开始存储p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i - 1] * P;           // 计算P^ih[i] = h[i - 1] * P + str[i];  // 计算前i个字符的哈希值}// ...后续处理查询
}

初始化过程详解

p[i] = P^i：预计算幂次，用于后续子串哈希计算。
h[i] = h[i-1] * P + str[i]：递推计算前缀哈希值。

示例（假设 str = "ABC"，P=131）：

h[0] = 0
h[1] = h[0]*131 + 'A' = 65
h[2] = h[1]*131 + 'B' = 65*131 + 66 = 8581
h[3] = h[2]*131 + 'C' = 8581*131 + 67 = 1123988

2.3 子串哈希计算

Ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}

公式解析

H(S[l..r])=H(r)−H(l−1)×Pr−l+1H(S[l..r])=H(r)−H(l−1)×Pr−l+1

h[r]：前 r 个字符的哈希值。
h[l-1] * p[r-l+1]：前 l-1 个字符的哈希值左移到对齐位置。

示例（计算 "BC" 在 "ABC" 中的哈希值）：

get(2, 3) = h[3] - h[1]*p[2] = 1123988 - 65*17161 = 1123988 - 1115465 = 8523

2.4 查询处理

while (m--) {int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2))printf("Yes\n");elseprintf("No\n");
}

能：比较两个子串 str[l1..r1] 和 str[l2..r2] 是否相同。

3. 流程图详解

以下是代码执行的流程图：

graph TDA[开始] --> B[输入n,m和字符串str]B --> C[初始化p[0]=1, h[0]=0]C --> D[循环i=1到n]D --> E[计算p[i] = p[i-1] * P]E --> F[计算h[i] = h[i-1] * P + str[i]]F --> DD --> G[输入查询次数m]G --> H[循环m次]H --> I[输入l1,r1,l2,r2]I --> J[计算Hash1=get(l1,r1)]I --> K[计算Hash2=get(l2,r2)]J --> L{Hash1 == Hash2?}K --> LL --> |Yes| M[输出"Yes"]L --> |No| N[输出"No"]M --> HN --> HH --> O[结束]

4. 关键问题解答

4.1 为什么选择P=131？

131是一个经验值，满足：
- 足够大以减少冲突。
- 是质数，保证哈希分布均匀。
其他常见选择：13331、99991等。

4.2 如何处理哈希冲突？

理论上，unsigned long long 自然溢出相当于模 264264，冲突概率极低。
如果需绝对准确，可双哈希（用两个不同的P计算）。

4.3 时间复杂度分析

操作	时间复杂度
初始化哈希数组	O(n)
单次子串比较	O(1)
m次查询	O(m)

5. 应用场景

快速子串匹配（如Rabin-Karp算法）。
最长回文子串（结合二分搜索）。
文本去重（比较哈希值而非原始字符串）。

6. 完整代码

#include <stdio.h>
#include <string.h>#define N 100010
#define P 131typedef unsigned long long Ull;Ull h[N], p[N];Ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}int main() {int n, m;char str[N];scanf("%d%d", &n, &m);scanf("%s", str + 1);p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + str[i];}while (m--) {int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2))printf("Yes\n");elseprintf("No\n");}return 0;
}

字符串哈希通过前缀哈希+幂次预处理实现O(1)子串比较。
P的选择和自然溢出是关键优化点。
适用于需要频繁比较子串的场景，比直接暴力匹配高效得多。

字符串哈希算法详解：原理、实现与应用

字符串哈希是一种高效处理字符串匹配和比较的技术，它通过将字符串映射为一个唯一的数值（哈希值），从而在O(1)时间内完成子串的比较。本文将结合代码实现，详细讲解前缀哈希法的工作原理，并通过流程图逐步解析…...

编程日记 2025/9/21 11:56:43

python-Leetcode 65.搜索旋转排序数组

题目： 整数数组nums按升序排列，数组中的值互不相同在传递给函数之前，nums在预先未知的某个小标K上进行了旋转，使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]，小标从0开始计数。…...

编程日记 2025/9/21 10:36:00

蓝桥杯 C/C++ 组历届真题合集速刷（二）

一、0ASC - 蓝桥云课 （单位换算）算法代码： #include <iostream> using namespace std; int main() {printf("%d",L);return 0; } 二、0时间显示 - 蓝桥云课 （单位换算）算法代码： #inclu…...

编程日记 2025/9/21 5:13:55

react的redux总结

目录一、Antd 1.1、基本使用 1.2、自定义主题二、Redux 2.1、工作流程 2.2、理解react-redux 2.3、优化 2.3.1、简写mapDispatch 2.3.2、Provider组件 2.4、数据共享 2.4.1、编写Person组件 2.4.2、Person组件的reducer 2.4.3、完成数据共享 2.5、求和案例 2.…...

编程日记 2025/9/18 19:27:54

MySQL视图

一、视图的本质与分类 1. 定义虚拟表：视图不存储数据，本质是保存的查询语句（SELECT），每次访问视图时动态执行查询并返回结果。逻辑抽象：基于一个或多个基表（或视图）创建&#xf…...

编程日记 2025/9/16 7:53:18

程序化广告行业（69/89）：电商素材制作与展示策略解析

程序化广告行业（69/89）：电商素材制作与展示策略解析在如今数字化营销的浪潮中，程序化广告成为众多企业精准触达目标客户的有力武器。作为一名在广告技术领域摸爬滚打多年的从业者，深知学习是不断进步的阶梯&#xff…...

编程日记 2025/9/20 6:58:33

【PCB工艺】发光二极管的原理

你真的知道发光二极管为什么会发光吗？ 而为什么另一部分二极管不会发光呢？ 这篇文章解释元器件发光二极管（LED）的底层原理。发光二极管（LED, Light Emitting Diode） 是一种能够将电能转换为光能的半导体…...

编程日记 2025/9/20 20:18:40

探秘 DeepSeek：开源生态如何推动 AI 技术普惠？

探秘 DeepSeek：开源生态如何推动 AI 技术普惠？引言在人工智能（AI）领域，技术的快速发展和广泛应用正在深刻改变我们的生活。然而，AI 的发展往往伴随着资源和技术的集中化问题，大型科技公司凭借其雄厚的资金和人才优势占据了主导地位，而中小企业、研究机构和个人开发…...

编程日记 2025/9/15 4:48:15

远程主机可能不符合glibc和libstdc++ VS Code服务器的先决条件

这是因为我最近更新了vscode， 服务器中有个GLIBC库，VSCode>1.86.0版本对低于v2.28.0版本的GLIBC不再满足需求。解决办法回退到之前能够连接服务器的版本。我之前用的是January 2025 (version 1.97) vscode旧版本下载地址...

编程日记 2025/9/9 1:34:21

JVM性能调优：参数配置×内存诊断×GC调优实战

🚀前言 “你的Java应用是否还在经历莫名卡顿？半夜被OOM报警惊醒？GC日志像天书看不懂？ 本文将用20个真实案例50个关键参数，带你掌握： 参数调优：如何用-XX:UseG1GC让GC暂停从秒级降到毫秒级&…...

编程日记 2025/9/15 4:48:19

pg_waldump 使用方法和输出验证

目录 pg_waldump 使用方法和输出验证一、pg_waldump 基础用法二、验证输出文件正确性三、关键参数 -p 的作用四、验证示例五、注意事项 pg_waldump 使用方法和输出验证一、pg_waldump 基础用法命令格式 pg_waldump [选项] [WAL文件路径]-p, --pgdataDIR：指定 Pos…...

编程日记 2025/9/4 6:32:11

Android 定制飞行模式和通话中设置菜单置灰

业务背景定制需求实现目标：通话中禁用移动网络设置中的网络模式和APN入口。 Google原生行为分析在原生Android中： 飞行模式： 无法在通话中开启：系统会自动阻止，因飞行模式会断开通话所需的射频。APN/网络模式修改…...

编程日记 2025/9/12 21:58:08

C# System.Text.Json 中 ReferenceHandling 使用详解

总目录一、什么是 ReferenceHandling？ 1. 概述 ReferenceHandling 是 System.Text.Json 中用于处理对象引用（循环引用或重复引用）的选项。它允许开发者在序列化和反序列化时控制如何处理对象之间的引用关系。默认情况下，Syst…...

编程日记 2025/9/12 5:19:10

【开发经验】调试OpenBMC Redfish EventService功能

EventService功能是Redfish规范中定义的一种事件日志的发送方式。用户可以设置订阅者信息(通常是一个web服务器)，当产生事件日志时，OpenBMC可以根据用户设置的订阅者信息与对日志的筛选设置，将事件日志发送到订阅者。相比于传统的SNMPTrap日…...

编程日记 2025/9/20 8:49:02

【AI工具】FastGPT：开启高效智能问答新征程

前言在人工智能飞速发展的当下，各类 AI 工具如雨后春笋般涌现。FastGPT 作为一款基于大语言模型（LLM）的知识图谱问答系统，凭借其强大的数据处理和模型调校能力，为用户带来了便捷的使用体验。今天，就让我们…...

编程日记 2025/9/21 4:55:56

4.8学习总结贪心算法+Stream流

贪心算法： 找到局部最优->从而推导全局最优。 Java练习： 获取随机验证码： import java.util.*; import java.util.function.BiConsumer; public class test {public static void main(String[] args) {System.out.println(createCode(…...

编程日记 2025/9/16 7:24:04

入选ICLR‘25 Spotlight！深度强化学习(DRL)迎来新突破！

近年来，深度强化学习相关的成果在顶会顶刊上接受度普遍较高，经常上榜ICLR、Nature、Science等。比如ICLR 2025上的一篇Spotlight，由清华团队提出，介绍了一种SmODE网路，让深度强化学习的控制更加丝滑！ 另外…...

编程日记 2025/9/18 12:52:40

【学习笔记】HTTP和HTTPS的核心区别及工作原理

一、基础概念 HTTP（超文本传输协议）：明文传输数据，默认端口80，容易被窃听或篡改。 HTTPS（HTTP SSL/TLS）：通过加密传输数据，默认端口443，保障安全性。二、…...

编程日记 2025/9/11 18:27:53

gbase8s之数据字典导出脚本（完美）

有时我们需要将表结构转换成数据库设计文档（WORD或者其他格式），这时需要使用脚本将表结构导出，转换成可用格式。该脚本适用于GBase 8s小版本号在3.0之后的版本（含有syscolumnsext、syscomments以及syscolcomments表&a…...

编程日记 2025/9/16 3:54:22

java整合socket通信全流程

前言大家好，由于工作上业务的需要，在java项目中引入了socket通信，特此记录一下，用以备份，本文章中的socket通信实现了，服务端与客户端的双向通讯，以及二者之间的心跳通信，服务端重启之后，客户端的自动重连功能。原理 Socket通信是计算机网络中常用的一种通信机制…...

编程日记 2025/9/6 20:38:46

【scikit-learn基础】--『预处理』之正则化

数据的预处理是数据分析，或者机器学习训练前的重要步骤。通过数据预处理，可以提高数据质量，处理数据的缺失值、异常值和重复值等问题，增加数据的准确性和可靠性整合不同数据，数据的来源和结构可能多种多样&#xff…...

编程日记 2025/9/18 17:29:17

WHAT - React 使用 Hook 分离计算逻辑与渲染逻辑

目录原始代码如何优化1. 函数式简洁风格2. hook 封装（重点）3. 性能优化原始代码 const GoodList ({ goods }) > {if (goods.length 0) {return <>暂无数据</>;}let totalCount 0;let totalPrice 0;goods.forEach((good) > {tot…...

编程日记 2025/9/19 7:01:46

AI比人脑更强，因为被植入思维模型【49】冰山理论思维模型

giszz的理解：冰山一角，冰山理论并不深奥，就是这个意思。对我启发比较大的，就是人的一个行为，背后可能藏着行为、应对方式、感受、观点、期待、渴望、自我七个层次。更有一个扩展，就是每个人的自我&#xff…...

编程日记 2025/9/20 16:34:45

【Linux】Git的简单使用

📝前言： 这篇文章我们来讲讲版本控制器Git，主要掌握一些简单的本地仓库与远端仓库之间的文件传输操作。 🎬个人简介：努力学习ing 📋个人专栏：Linux 🎀CSDN主页愚润求学 &#x1f30…...

编程日记 2025/9/9 18:34:51

【WebRTC】开源项目Webrtc-streamer介绍

WebRTC-Streamer 这是一个用于通过简单的信令机制（参见 api）流式传输 WebRTC 媒体源的实验项目，支持以下媒体源： 捕获设备屏幕捕获 mkv 文件 RMTP/RTSP 源同时该项目也兼容 WHEP 接口。注意 * 在线演示已停止&#xff0c…...

编程日记 2025/9/7 1:27:40

Bigemap pro制作行政区域图

Bigemap pro制作行政区域图第一步：打开bigemap pro软件，右上角加载更多矢量到地图上，加载出来需要的矢量数据，以北京市为例，如图所示： 第二步：在我的矢量图层，点击右键&#xff0c…...

编程日记 2025/9/7 15:35:24

Kotlin 和 spring-cloud-function 兼容问题

错误： [ERROR] Failed to execute goal org.jetbrains.kotlin:kotlin-maven-plugin:1.9.25:compile (compile) on project springdoc-openapi-starter-common: Compilation failure [ERROR] /opt/repository/org/springframework/cloud/spring-cloud-function-conte…...

编程日记 2025/9/12 1:22:43

OpenVINO是什么

OpenVINO（Open Visual Inference and Neural Network Optimization）是由英特尔（Intel）开发的一个开源工具套件，用于优化和加速深度学习模型的推理过程，特别是在计算机视觉、自然语言处理和生成式 AI 等领域…...

编程日记 2025/9/10 21:54:39

【学Rust写CAD】38 over_in 函数(alpha256补充方法）

源码 #[inline] // 内联优化标记 pub fn over_in(self, src: Argb, dst: Argb) -> Argb {// 计算目标alpha因子 self * src的alpha通道let dst_alpha self * src.alpha_t();// 预乘源和目标的颜色分量let src_rb src.rb() * self.0; // 源的红蓝分量乘以alpha因子let …...

编程日记 2025/9/14 12:41:05

球类（继承和多态）

父类Ball，设置为抽象类，调用get和set方法创建对象，将子类重写的功能函数抽象化。 // 抽象球类 abstract class Ball {private String name;private double radius; // 半径private double weight; // 重量private double price; // 价格// 构…...

编程日记 2025/9/10 6:35:29

苍穹外卖（1）-部分环境配置（git、数据库）

首先配置git 创建好本地仓库之后把项目弄到远程仓库里去先进行提交 ，后进行推送 ，然后gitee创建一个仓库把这个url复制好推送后会出来一个点击推送，会让你输入gitee账号密码，输入自己的账号密码，就可以连接远程仓…...

编程日记 2025/9/10 1:29:22

避免误用strncmp与memcmp，strcpy与memcpy

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu) 注：使用说明部分参考豆包ai 1. 字符串与二进制流认知许多时候，我们作为软件研发人员，会觉得一段内存就是一串字符串；字符串就是一段内存； 概念上&#xff…...

编程日记 2025/9/21 4:33:46

华为欧拉系统安装docker

华为欧拉系统安装docker cat /etc/openEuler-release sudo yum-config-manager --add-repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo vi /etc/yum.repos.d/docker-ce.repo dnf makecache dnf install https://download.docker.com/linux/centos…...

编程日记 2025/9/21 1:20:05

windows11怎么把notepad++添加到鼠标右键菜单？

在Windows 11中将Notepad添加到鼠标右键菜单，可通过以下两种方法实现： 方法一：手动修改注册表（推荐） 打开注册表编辑器按下 Win R，输入 regedit 并回车 1 2 3 。定位注册表路径…...

编程日记 2025/9/19 12:31:26

HTML5笔记：什么是HTML

HTML的全称为超文本标记语言，是一种标记语言。它包括一系列标签，通过这些标签可以将网络上的文档格式统一，使分散的Internet资源连接为一个逻辑整体。HTML文本是由HTML命令组成的描述性文本，HTML命令可以说明文字，图形…...

编程日记 2025/9/19 2:11:48

【WRF理论第十五期】WPS中输入geogrid二进制格式

WPS中输入geogrid二进制格式基本概念：Geogrid二进制格式支持的数据类型 geotiff→tiff的规则说明类型1：主导类别字段（Dominant Category Field）类型2：连续字段（Continuous Field）类型3&#xf…...

编程日记 2025/9/10 10:03:04

《UNIX网络编程卷1：套接字联网API》第8章：基本UDP套接字编程深度解析

《UNIX网络编程卷1：套接字联网API》第8章：基本UDP套接字编程深度解析（8000字图文实战） 一、UDP协议核心特性与编程模型 1.1 UDP协议设计哲学 UDP（User Datagram Protocol） 是面向无连接的传输层协议&…...

编程日记 2025/9/2 21:00:21

【WPF】IOC控制反转的应用：弹窗但不互相调用ViewModel

全称：Inversion of Control，控制反转场景：A页面需要调用B/C页面等，防止直接在VM中新建别的页面实例，使用IOC设计架构； 创建Service，在Service中实现页面的实例创建和定义页面输入输出参数。在…...

编程日记 2025/9/10 14:42:16

解决制作CI流水线时的no host异常报错

方法介绍使用 HostAliases 向 Pod /etc/hosts 文件添加条目当dns配置以及其他选项不合理时，可以通过向pod的/etc/hosts添加条目，可以在pod级别覆盖对主机名的解析，可以通过pod spec的pod aliases来自定义添加条目。默认的hosts文件内容 …...

编程日记 2025/9/19 18:23:24

(AI+医疗)2025最应该学习是--医学AI大模型LLM应用与开发

(AI医疗)2025最应该学习是–医学AI大模型LLM应用与开发!! AI技术正在为医学领域带来的现实变革。而实现这一切的核心，正是自然语言大模型（LLM）的应用与开发。为什么医学AI是未来的风口？ AI正在重塑医疗行业。从智能问诊到辅助…...

编程日记 2025/9/18 15:54:49

MCP+Deepseck王炸组合 | 附实战操作及其MCPserver | 可替代Manus，实现AGI

MCP介绍 MCP 是一个开放协议，它为应用程序向 LLM 提供上下文的方式进行了标准化。你可以将 MCP 想象成 AI 应用程序的 USB-C 接口。就像 USB-C 为设备连接各种外设和配件提供了标准化的方式一样，MCP 为 AI 模型连接各种数据源和工具提供了标准化的接口。…...

编程日记 2025/9/19 18:18:40

STM32学习之ARM内核自带的中断

📢：如果你也对机器人、人工智能感兴趣，看来我们志同道合✨ 📢：不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢：文章若有幸对你有帮助，可点赞 👍…...

编程日记 2025/9/12 9:32:46

Java 设计模式：工厂模式详解

Java 设计模式：工厂模式详解工厂模式（Factory Pattern）是一种创建型设计模式，它通过将对象的创建过程封装到工厂类中，避免了直接使用 new 关键字创建对象，从而提高了代码的灵活性和可维护性。本文将介绍工…...

编程日记 2025/9/21 9:42:22

python内置标准模块--OS

内置标准模块–OS 在 Python 中，os 是一个内置标准模块，全称是 Operating System（操作系统）。它的核心作用是与当前操作系统交互，提供对文件系统、进程管理、环境变量等操作系统功能的访问接口 1. os 模块的核心功…...

编程日记 2025/9/12 20:33:09

echart实现动态折线图(vue3+ts)

最近接到个任务，需要用vue3实现动态折线图。之前没有用过，所以一路坎坷，现在记录一下，以后也好回忆一下。之前不清楚echart的绘制方式，以为是在第一秒的基础上绘制第二秒，后面实验过后，发现并…...

编程日记 2025/9/14 10:09:56

Web3（阶段一：入门）——椭圆曲线

一、快速概览 ECC 是一种基于有限域上椭圆曲线代数结构的公钥加密系统。它提供与 RSA 相当的安全性，但密钥长度要短得多，从而实现更快的计算速度和更低的资源使用率。ECC 广泛应用于各种应用，包括安全通信、数字签名和加密货币。二、什…...

编程日记 2025/9/12 22:21:36

vue总结

1.vue是什么。 vue是javascript和html结合后的，实现了html的模块开发，并且样式和js互不影响。组件内的javascript逻辑只在组件内有效，当然父类可通过某些方法调用，但是彼此间没有影响。各个组件的样式，通过scope防止了…...

编程日记 2025/9/20 15:17:12

LCR 131. 砍竹子 I

文章目录题意思路代码题意题目链接思路代码 class Solution { public:int cuttingBamboo(int bamboo_len) {if (bamboo_len 2)return 1;if (bamboo_len 3)return 2;if (bamboo_len 4)return 4;int x bamboo_len / 3;int ans pow(3, x);int y bamboo_len % 3;if …...

编程日记 2025/9/11 11:19:30

游戏引擎学习第210天

回顾并为今天的工作做准备今天我们，进行一些编码工作。这部分的编码内容对那些对代码架构感兴趣的人非常有帮助，我认为今天的编码内容会很有教育意义，尤其是在展示一些代码转化的过程中，希望大家能够从中获得一些启发。接下来…...

编程日记 2025/9/19 11:17:23

40--华为IPSec VPN实战指南：构建企业级加密通道

🛡️ 华为IPSec VPN实战指南：构建企业级加密通道 “当数据开始穿盔甲，黑客只能望’密’兴叹” —— 本文将手把手教你用华为设备搭建军用级加密隧道，从零开始构建网络长城！ 文章目录 🛡️ 华为IPSec VPN实战…...

编程日记 2025/9/19 4:29:56