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

算法提升之字符串练习-02（字符串哈希）

news 2025/7/18 9:23:07

今天给大家分享的是字符串中常会用的一种方法，叫做字符串哈希方法，相较于传统的前后缀找公共字符串，这种方法可以更好地理解。是通过将字符变为数值大小来进行判断是否包含前后缀。

例题分析

问题描述

小桥是一名喜欢研究文学的学生，最近她在研究一种名为“诗歌双联”的文学形式，它可以将两个诗句拼接在一起，形成新的诗句。为了更好地研究这种文学形式，小桥准备了两个字符串 s 和 t。

她发现，如果从字符串 s中选出两个长度为 k 的不相交子串，并将它们拼接在一起（不能改变相对顺序），可能会形成一个包含 t的字符串。为了验证这个想法，她想设计一种算法来检验是否可以这样做。

输入格式

第一行包含三个整数 n,m,k(2≤m≤2⋅k≤n≤104)，表示字符串 s 和字符串 t 的长度，以及可选子串的长度。

接下来两行是由小写字母组成的字符串 s 和 t。

输出格式

如果可以选出的两个子串，使得拼接后得到的字符串包含 t，则输出 "Yes"，否则输出 "No"。

输入案例：

7 4 3
baabaab
aaaa

输出案例：

Yes

代码部分：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef unsigned long long ull;
char s[N],t[N];
const int base=131;
ull bases[N],h1[N],h2[N];
int n,m,k;
ull gethash(int l,int r,ull s[]){return s[r]-s[l-1]*bases[r-l+1];}
int main()
{  cin>>n>>m>>k;cin>>s+1>>t+1;bases[0]=1;for(int i=1;i<=n;i++){bases[i]=bases[i-1]*base;h1[i]=h1[i-1]*base+(int)s[i];if(i<=m)h2[i]=h2[i-1]*base+(int)t[i];}for(int i=1;i+m-1<=n;i++)           //特判一下拆分t数组，一边把t数组全选的情况{if(gethash(i,i+m-1,h1)==gethash(1,m,h2)){cout<<"Yes"<<'\n';return 0;}}for(int i=1;i<m;i++)     //拆分t数组，选择两边有用的选的字符串长度，确保算哈希值的时候区间合法{if(i>k||m-i>k)continue;int l=k,r=n-k+1;while(l<r)           //确保没有重合,左边选择的字符放在前面{if(gethash(l-i+1,l,h1)==gethash(1,i,h2)&&gethash(r,r+m-i-1,h1)==gethash(i+1,m,h2)){cout<<"Yes"<<'\n';return 0;}if(gethash(l-i+1,l,h1)!=gethash(1,i,h2))l++;if(gethash(r,r+m-i-1,h1)!=gethash(i+1,m,h2))r--;}}cout<<"No"<<'\n';return 0;
}

这道题运用了字符串哈希的方法，其中核心是：

for(int i=1;i<m;i++)     //拆分t数组，选择两边有用的选的字符串长度，确保算哈希值的时候区间合法{if(i>k||m-i>k)continue;int l=k,r=n-k+1;while(l<r)           //确保没有重合,左边选择的字符放在前面{if(gethash(l-i+1,l,h1)==gethash(1,i,h2)&&gethash(r,r+m-i-1,h1)==gethash(i+1,m,h2)){cout<<"Yes"<<'\n';return 0;}if(gethash(l-i+1,l,h1)!=gethash(1,i,h2))l++;if(gethash(r,r+m-i-1,h1)!=gethash(i+1,m,h2))r--;}}

拆分逻辑：
- 将t拆分为两部分：前i个字符（t1）和后m-i个字符（t2）。
- 要求两部分长度都不超过k（因为每个子串长度最大为k）。
双指针搜索：
- l从k开始向右移动，r从n-k+1开始向左移动。
- 检查：
  - s中以l结尾的长度为i的子串是否等于t1。
  - s中以r开头的长度为m-i的子串是否等于t2。
  - 如果同时满足且两区间不相交（l < r），则输出 "Yes"。

2.理解l与m

一、先明确背景：拆分`t`为两部分

代码中通过i枚举拆分点，将t拆分为：

前半部分t1：t[1..i]（长度i）；
后半部分t2：t[i+1..m]（长度m-i）。

目标是在s中找到：

一个子串匹配t1；
另一个子串匹配t2；
两个子串长度均不超过k，且不相交。

二、`gethash(l-i+1, l, h1) == gethash(1, i, h2)` 解析

这部分用于判断s中的某个子串是否匹配t1（t的前i个字符）。

参数含义：

h1：字符串s的哈希数组（存储s的前缀哈希值）；
h2：字符串t的哈希数组（存储t的前缀哈希值）；
1, i, h2：
表示取t中从第1位到第i位的子串（即t1）的哈希值。
对应t的前半部分：t[1]t[2]...t[i]。
l-i+1, l, h1：
表示取s中从第l-i+1位到第l位的子串的哈希值。
这个子串的长度是i（因为l - (l-i+1) + 1 = i），与t1长度相同，用于匹配t1。

逻辑：

如果s中[l-i+1, l]区间的子串哈希值，与t中[1, i]区间的子串哈希值相等，则说明这两个子串完全匹配（忽略哈希冲突的小概率情况）。

三、`gethash(r, r+m-i-1, h1) == gethash(i+1, m, h2)` 解析

这部分用于判断s中的某个子串是否匹配t2（t的后m-i个字符）。

参数含义：

i+1, m, h2：
表示取t中从第i+1位到第m位的子串（即t2）的哈希值。
对应t的后半部分：t[i+1]t[i+2]...t[m]，长度为m-i。
r, r+m-i-1, h1：
表示取s中从第r位到第r+m-i-1位的子串的哈希值。
这个子串的长度是(r+m-i-1) - r + 1 = m-i，与t2长度相同，用于匹配t2。

逻辑：

如果s中[r, r+m-i-1]区间的子串哈希值，与t中[i+1, m]区间的子串哈希值相等，则说明这两个子串完全匹配。

四、为什么这样设计？

长度匹配：
- t1长度为i，因此s中匹配的子串长度也必须是i（l - (l-i+1) + 1 = i）。
- t2长度为m-i，因此s中匹配的子串长度也必须是m-i（(r+m-i-1) - r + 1 = m-i）。
位置约束：
- l是s中匹配t1的子串的结束位置（方便后续确保两子串不相交）。
- r是s中匹配t2的子串的起始位置（确保l < r即可保证两子串不相交）。
哈希函数特性：
gethash(l, r, h)的定义是计算h数组中[l..r]区间的哈希值，因此参数必须严格对应子串的起止位置才能正确比较。