字符串哈希动态规划_6

一.字符串哈希

字符串哈希概述

字符串哈希是一种将字符串映射到一个数值的技术，常用于处理字符串相关的算法问题，尤其在处理字符串匹配、子串查找等问题时非常高效。它的核心思想是利用一个哈希函数将字符串映射成一个整数，并根据该整数来判断字符串是否相等。

字符串哈希的结构

字符串哈希的结构包括：

  1. 哈希值（Hash Value）：通过某种算法计算得到的一个整数值，代表该字符串的“身份”。
  2. 哈希函数：将字符串映射到哈希值的公式或算法。常见的哈希函数基于多项式哈希或者改进后的滚动哈希。
  3. 哈希表：一种存储字符串哈希值的容器，通常使用数组或字典。
哈希函数：多项式哈希

一个常见的字符串哈希函数是基于多项式的哈希：

给定一个字符串 s = s_0 s_1 s_2 ... s_n-1，其哈希值可以通过如下公式计算：

  • p 是一个常数基数，通常选择一个小的质数（例如 31 或 53）。
  • m 是模数，用于避免哈希值过大，通常选择一个大质数。
  • s_i 是字符串中的每个字符转换为整数后的值，通常是字符的 ASCII 码或字母位置。

字符串哈希的功能

  1. 高效比较：通过哈希值，两个字符串的相等性可以通过哈希值的比较来实现，避免逐字符对比，提高效率。
  2. 子串查找：通过哈希技术，快速计算任意子串的哈希值，可以用于解决许多字符串匹配的问题。
  3. 避免重复：哈希值可以帮助快速去重，例如在长字符串中查找重复的子串。

  4. 在线算法：滚动哈希支持在线更新，即当一个子串被扩展或者滑动时，可以通过常数时间更新哈希值。

代码实现

// 俩字符串是否相等
#include <iostream>
#include <string>
#include <cmath>const int p = 31;
const int m = 1e9 + 7;long long compute_hash(const std::string &s) {long long hash_value = 0;long long p_pow = 1;for (char c : s) {hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;p_pow = (p_pow * p) % m;}return hash_value;
}int main() {std::string s1 = "hello";std::string s2 = "hello";if (compute_hash(s1) == compute_hash(s2)) {std::cout << "Strings are equal." << std::endl;} else {std::cout << "Strings are not equal." << std::endl;}return 0;
}

/*2. 滚动哈希（子串比较）
通过滚动哈希，我们可以高效地比较字符串中的任意子串。在这个过程中，哈希值会根据前一个哈希值和新加入的字符更新。
*/
#include <iostream>
#include <string>
#include <vector>const int p = 31;
const int m = 1e9 + 7;std::vector<long long> compute_prefix_hash(const std::string &s) {int n = s.size();std::vector<long long> prefix_hash(n + 1, 0);long long p_pow = 1;for (int i = 0; i < n; ++i) {prefix_hash[i + 1] = (prefix_hash[i] + (s[i] - 'a' + 1) * p_pow) % m;p_pow = (p_pow * p) % m;}return prefix_hash;
}long long get_substring_hash(int l, int r, const std::vector<long long> &prefix_hash) {long long hash_value = prefix_hash[r + 1] - prefix_hash[l];if (hash_value < 0) hash_value += m;return hash_value;
}int main() {std::string s = "abcdef";auto prefix_hash = compute_prefix_hash(s);// 比较 s[1..3] 和 s[2..4] 是否相同if (get_substring_hash(1, 3, prefix_hash) == get_substring_hash(2, 4, prefix_hash)) {std::cout << "Substrings are equal." << std::endl;} else {std::cout << "Substrings are not equal." << std::endl;}return 0;
}

二.题

1.

思路：A - B = C可以变为 A - C = B，通过统计每个数字出现的次数，然后对其本身a[i] -= C，对映映射到map里的位置就是B 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <map>using namespace std;
using LL = long long;LL a[200001];
map<LL, LL> m; int main() {int n;LL c;LL ans = 0;cin >> n >> c;for (int i = 1; i <= n; i++) {cin >> a[i];m[a[i]]++;a[i] -= c;}for (int i = 1; i <= n; i++) ans += m[a[i]];cout << ans << endl;return 0;
}

2.

 思路：根据题意，字符串哈希统计每个位置的前缀哈希值，通过for对字符串a和字符串b的前缀和后缀的哈希值进行比对，求最大值

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <map>using namespace std;const int N = 110, base = 131;
long long p[N], hl[N], hr[N];
char stra[N], strb[N];
int lena, lenb, lmax;long long get(long long h[], int l, int r){return h[r] - h[l - 1] * p[r - l + 1];
} 
int main(){int i, j, res = INT_MIN;scanf("%s%s", stra + 1, strb + 1);lena = strlen(stra + 1);lenb = strlen(strb + 1);lmax = max(lena, lenb); p[0] = 1;for (i = 1; i <= lena; i++) hl[i] = hl[i - 1] * base + (stra[i] - 96);for (i = 1; i <= lenb; i++) hr[i] = hr[i - 1] * base + (strb[i] - 96);for (i = 1; i <= lmax; i++) p[i] = p[i - 1] * base;for (i = 1; i <= lmax; i++){int al, bl;if (lena < i || lenb < i) break; al = get(hl, 1, i) != get(hr, lenb - i + 1, lenb) ? INT_MIN : i;bl = get(hl, lena - i + 1, lena) != get(hr, 1, i) ? INT_MIN : i;  res = max(res, max(al, bl)); }printf("%d\n", res);return 0; 
}

3.

思路 ：用集合来储存每个不同字符串的哈希值，最后求集合的长度即可

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <map>
#include <set>using namespace std;const int m = 131;
const int p = 1e9 + 7;int prefix_hash(string& s) {int p_pow = 1;int prefix = 0;for (int i = 0; i < s.size(); i++) {prefix = (prefix + (s[i] - 'a' - 1) * p_pow) % p;p_pow = (p_pow * m) % p;}return prefix;
}int main(){int n; cin >> n;vector<string>s(n+1);set<int>sett;for (int i = 1; i <= n; i++) {cin >> s[i];int temp = prefix_hash(s[i]);sett.insert(temp);}int coun = sett.size();cout << coun;return 0; 
}

4.

思路： 用哈希表存集合，每个单词都有对于的文章，通过输入的单词找文章即可

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>using namespace std;int main() {int n;cin >> n;map<string, set<int>> word_to_passages;for (int i = 1; i <= n; i++) {int words;cin >> words;for (int j = 0; j < words; j++) {string word;cin >> word;word_to_passages[word].insert(i);}}int m;cin >> m;while (m--) {string word;cin >> word;if (word_to_passages.find(word) != word_to_passages.end()) {for (int passage : word_to_passages[word]) {cout << passage << " ";}}cout << endl;}return 0;
}

5.

思路：哈希集合+容器

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>using namespace std;int main(){int t; cin >> t;while (t--) {int n; cin >> n;vector<int>tt;unordered_set<int>ttt;for (int i = 1; i <= n; i++) {int temp; cin >> temp;if (ttt.find(temp) == ttt.end()) {tt.push_back(temp);ttt.insert(temp);}}for (int i = 0; i < tt.size(); i++) {cout << tt[i] << " ";}cout << endl;}return 0; 
}

6.算法竞赛进阶指南 

思路：用埃拉托斯特尼筛法

#include <iostream>
#include <vector>
using namespace std;const int MAX_N = 100000000; void sieve_of_eratosthenes(int n, vector<int>& primes) {vector<bool> is_prime(n + 1, true);is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; ++i) {if (is_prime[i]) {for (int j = i * i; j <= n; j += i) {is_prime[j] = false;}}}for (int i = 2; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}}
}int main() {ios::sync_with_stdio(0); int n, q;cin >> n >> q;vector<int> primes;sieve_of_eratosthenes(n, primes);while (q--) {int k;cin >> k;cout << primes[k - 1] << endl; }return 0;
}

三.动态规划

状态机 DP（Dynamic Programming, 状态机动态规划）

状态机DP是一种将动态规划（DP）与有限状态机（FSM, Finite State Machine）相结合的策略。它通常用于解决一些有多个状态转换的问题，每个状态依赖于前一个状态或多个前状态的结果。

核心思想

状态机 DP 是将问题的状态划分成若干个不同的子问题，使用 DP 来保存每个状态的结果，并在状态之间进行转移。每次状态转移时会考虑当前状态和之前状态的关系，通常通过某些条件进行转换。

在很多实际问题中，可以通过建模成状态机，明确每个状态的含义，并根据问题的具体要求来设计状态转移的规则和相应的 DP 转移方程。

一般步骤

  1. 定义状态：明确在问题中你需要维护哪些状态，可以是某个数值的集合，也可以是某些特定的条件或标志。

  2. 状态转移：定义如何从当前状态转移到下一个状态。转移条件通常由问题本身的限制或约束决定。

  3. 递推关系：写出状态转移方程，描述从前一个状态如何得到当前状态的值。

  4. 初始化：定义状态的初始值，通常是边界条件。

  5. 答案：根据最终的状态或者状态值来得到问题的答案。

状态机 DP 的经典应用

  1. 多重背包问题：通过状态来记录背包的容量和物品的状态，进行状态转移。
  2. 字符串匹配：例如求解正则表达式的匹配问题，或者KMP算法的状态机。
  3. 最短路径问题：特别是在有多个条件和约束的情况下，状态机可以很好地建模状态和转移。
  4. 路径规划问题：比如在网格中进行路径搜索，并在状态机中管理每个路径的不同状态。

例子1：0-1背包问题的状态机 DP

我们可以将 0-1 背包问题中的状态定义为背包的容量。状态机 DP 的状态就是当前已放入背包的物品集合的状态。

问题：有一个背包容量为 W，现在有 N 个物品，第 i 个物品的重量为 wi，价值为 vi。要求在不超过背包容量的情况下，使得背包中的物品总价值最大。
状态定义：
  • dp[i][w]：表示前 i 个物品，背包容量为 w 时的最大价值。
状态转移：
  • 不选择第 i 个物品：dp[i][w] = dp[i-1][w]
  • 选择第 i 个物品：dp[i][w] = dp[i-1][w - wi] + vi（前提是 w >= wi）
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n, W;cin >> n >> W;vector<int> w(n), v(n);// 输入物品的重量和价值for (int i = 0; i < n; i++) {cin >> w[i] >> v[i];}// dp[w]表示背包容量为w时的最大价值vector<int> dp(W + 1, 0);for (int i = 0; i < n; i++) {// 从后往前遍历避免重复计算for (int j = W; j >= w[i]; j--) {dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}}cout << dp[W] << endl;  // 输出最大价值return 0;
}

 

解释：
  • dp[j] 表示容量为 j 时的最大价值。
  • 对于每个物品 i，我们从后向前遍历容量 W，更新背包的最大价值。

例子2：字符串匹配（正则表达式）中的状态机 DP

在正则表达式匹配问题中，可以通过状态机来表示正则表达式的每个状态。

问题：给定一个字符串 s 和一个模式 p，判断 s 是否与模式 p 匹配，模式中的 . 可以匹配任意字符，* 可以匹配零个或多个前面的字符。
状态定义：
  • dp[i][j]：表示 s[0..i-1] 是否与 p[0..j-1] 匹配。
状态转移：
  • 如果 p[j-1] 是 *：
    • dp[i][j] = dp[i][j-2] 或者 dp[i-1][j]（即 * 匹配零次或多次）
  • 如果 p[j-1] 是 . 或者 s[i-1] == p[j-1]：
    • dp[i][j] = dp[i-1][j-1]
#include <iostream>
#include <vector>
#include <string>using namespace std;bool isMatch(const string& s, const string& p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));dp[0][0] = true;  // 空串和空模式是匹配的// 处理模式中以 * 开头的情况for (int j = 1; j <= n; j++) {if (p[j - 1] == '*') {dp[0][j] = dp[0][j - 2];}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];} else if (p[j - 1] == '*') {dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));}}}return dp[m][n];
}int main() {string s = "aa";string p = "a*";if (isMatch(s, p)) {cout << "Matched!" << endl;} else {cout << "Not matched!" << endl;}return 0;
}

 

结论

  • 状态机 DP 结合了动态规划的思想和状态机的建模，通过定义状态、转移规则和递推关系，解决了很多具有状态转移性质的问题。
  • 典型的应用包括多重背包问题、字符串匹配问题、最短路径问题等。
  • 在使用状态机 DP 时，要重点理解状态的定义，状态之间的转移条件，以及如何通过 DP 更新每个状态的值。

 

 四.题

1.

思路：由题来模拟整个天数的交易过程，每次都做出最优解

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector f(n + 1, vector<array<int, 2>>(k + 2, {INT_MIN / 2, INT_MIN / 2}));for (int j = 1; j <= k + 1; j++) {f[0][j][0] = 0;}for (int i = 0; i < n; i++) {for (int j = 1; j <= k + 1; j++) {f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + prices[i]);f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - prices[i]);}}return f[n][k + 1][0];}
};

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/19698.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Kubernetes控制平面组件：Kubernetes如何使用etcd

Kubernetes控制平面组件：Kubernetes如何使用etcd

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…
阅读更多...
Mybatis后端数据库查询多对多查询解决方案

Mybatis后端数据库查询多对多查询解决方案

问题场景&#xff1a; 我开发的是一个论文选择系统。 后端用一个论文表paper来存储论文信息。 论文信息中&#xff0c;包含前置课程&#xff0c;也就是你需要修过这些课程才能选择这个论文。 而一个论文对应的课程有很多个。 这样就造成了一个数据库存储的问题。一个paper…
阅读更多...
BGP配置华为——RR反射器配置

BGP配置华为——RR反射器配置

实验拓扑 与之前实验同理将loop0作为routerID使用&#xff0c;且R1和R2上用loop1接口用于模拟用户其他网段 实验要求 1&#xff0c;在AS100内运行OSPF协议 2.配置路由反射器&#xff0c;使得从R1进入的数据能够反射到全局网络 3.在R1和R2上分别宣告自己的loop1口网段用于观…
阅读更多...
CentOS7 离线安装 Postgresql 指南

CentOS7 离线安装 Postgresql 指南

一、背景 服务器通常都是离线内网环境&#xff0c;想要通过联网方式一键下载安装 Postgresql 不太现实&#xff0c;本文将介绍如何在 CentOS7 离线安装 Postgresql&#xff0c;以及遇到困难如何解决。 二、安装包下载 先在本地下载好 rpm 包&#xff0c;再通过 ftp 上传到服…
阅读更多...
vue3项目实践心得-寻找未被使用的最小编号

vue3项目实践心得-寻找未被使用的最小编号

&#x1f9e1;&#x1f9e1;遇到的问题&#x1f9e1;&#x1f9e1; 在用vue3ts编写编译原理项目中”绘制状态转换图“时&#xff0c;有一个添加状态的功能按钮&#xff0c;用户点击按钮即可添加一个新的状态&#xff0c;至于新的状态的编号值&#xff0c;想着以”最小未被使用…
阅读更多...
FPGA简介|结构、组成和应用

FPGA简介|结构、组成和应用

Field Programmable Gate Arrays&#xff08;FPGA&#xff0c;现场可编程逻辑门阵列&#xff09;&#xff0c;是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物&#xff0c; 是作为专用集成电路&#xff08;ASIC&#xff09;领域中的一种半定制电路而出现的&#xff0c…
阅读更多...
C# 入门简介

C# 入门简介

关于C# ​ C# &#xff08;读作C Sharp&#xff09;是由微软公司开发的一种面向对象、类型安全、高效且简单的编程语言&#xff0c;最初于 2000 年发布&#xff0c;并随后成为 .NET 框架的一部分。所以学习C#语言的同时&#xff0c;也是需要同步学习.NET框架的&#xff0c;不过…
阅读更多...
处理使用 mapstruct 导致分页总数丢失问题

处理使用 mapstruct 导致分页总数丢失问题

问题 PageHelper 分页总数不对&#xff0c;返回的总数老是等于当前页数目 分析 问题出现在 domain 转 VO 这个步骤&#xff0c;当我把数据库实体类型的 list 转为 vo 类型的 list&#xff0c;然后放进 PageInfo 则会丢失分页信息&#xff1b; 解决方式 从数据库查询出来后…
阅读更多...
LabVIEW中的icon.llb 库

LabVIEW中的icon.llb 库

icon.llb 库位于 C:\Program Files (x86)\National Instruments\LabVIEW 2019\vi.lib\Platform 目录下&#xff0c;是 LabVIEW 系统中的一个重要库。它的主要功能是与图标相关的操作&#xff0c;提供了一些实用的 VI 用于处理 LabVIEW 图标的显示、修改和设置。通过该库&#x…
阅读更多...
【ProtoBuf】文件编写及序列化

【ProtoBuf】文件编写及序列化

ProtoBuf文件编写及序列化 文章目录 ProtoBuf文件编写及序列化快速上手ProtoBuf创建.proto 文件指定Proto3语法Package声明符定义消息(message)定义消息字段编译命令 序列化与反序列化的使用小结 快速上手ProtoBuf 为了快速上手以及完整的使用ProtoBuf&#xff0c;我们将编写一…
阅读更多...
Java高频面试之SE-22

Java高频面试之SE-22

hello啊&#xff0c;各位观众姥爷们&#xff01;&#xff01;&#xff01;本baby今天又来了&#xff01;哈哈哈哈哈嗝&#x1f436; Java中的Optional了解多少&#xff1f; 在 Java 中&#xff0c;Optional 是 Java 8 引入的一个容器类&#xff0c;用于显式处理可能为 null 的…
阅读更多...
250217-数据结构

250217-数据结构

1. 定义 数据结构是数据的存储结构&#xff0c;即数据是按某些结构来存储的&#xff0c;比如线性结构&#xff0c;比如树状结构等。 2. 学习意义 数据结构是服务于算法的&#xff0c;为了实现算法的高效计算&#xff0c;所以将数据按特定结构存储。比如使用快速插入或删除的…
阅读更多...
PyCharm2024使用Python3.12在Debug时，F8步进时如同死机状态

PyCharm2024使用Python3.12在Debug时，F8步进时如同死机状态

在使用时PyCharm2024&#xff0b;Python3.12&#xff0c;在程序进行调试时&#xff0c;按F8步进时如同死机状态。 1、相同的程序在PyCharm2023&#xff0b;Python3.9时是没有问题的&#xff0c;因此决定重装PyCharm2023&#xff0b;Python3.9&#xff0c;进行调试——调试OK。 …
阅读更多...
C/C++ | 每日一练 (2)

C/C++ | 每日一练 (2)

&#x1f4a2;欢迎来到张胤尘的技术站 &#x1f4a5;技术如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 C/C | 每日一练 (2)题目参考答案封装继承多态虚函数底…
阅读更多...
DeepSeek应用-一秒对书本要点分析并创建思维脑图

DeepSeek应用-一秒对书本要点分析并创建思维脑图

2025年开始啦&#xff0c;从DeepSeek的火爆程度来看&#xff0c;今年必须紧盯DS的发展&#xff0c;AI不会淘汰人&#xff0c;AI只会淘汰不会使用的人。从文心一言、豆包、Kimi到DS,基本上从功能上大致相同&#xff0c;但是DeepSeek的开源着实在眼界和格局上更胜一筹&#xff0c…
阅读更多...
4、IP查找工具-Angry IP Scanner

4、IP查找工具-Angry IP Scanner

在前序文章中&#xff0c;提到了多种IP查找方法&#xff0c;可能回存在不同场景需要使用不同的查找命令&#xff0c;有些不容易记忆&#xff0c;本文将介绍一个比较优秀的IP查找工具&#xff0c;可以应用在连接树莓派或查找IP的其他场景中。供大家参考。 Angry IP Scanner下载…
阅读更多...
android 的抓包工具

android 的抓包工具

charles 抓包工具 官网地址 nullCharles Web Debugging Proxy - Official Sitehttps://www.charlesproxy.com/使用手册一定记得看官网 SSL Certificates • Charles Web Debugging Proxy http请求&#xff1a; 1.启动代理&#xff1a; 2.设置设备端口 3.手机连接当前代理 …
阅读更多...
Java常用工具类详解

Java常用工具类详解

目录 一、Java 中的数学利器&#xff1a;java.lang.Math 类详解 1.常用属性 2.常用方法 ⑴.static int abs(int a) ⑵.static double ceil(double a) ⑶.static double floor(double a) ⑷.static int max(int a, int b) 和 static int min(int a, int b) ⑸.static do…
阅读更多...
STM32 低功耗模式

STM32 低功耗模式

目录 背景 低功耗模式 睡眠模式 进入睡眠模式 退出睡眠模式 停止模式 进入停止模式 退出停止模式 待机模式 进入待机模式 退出待机模式 程序 睡眠模式 休眠模式配置 进入休眠模式 退出睡眠模式 停止模式 停止模式配置 进入停止模式 退出停止模式 待机模式…
阅读更多...
uniapp 使用v-html在微信小程序中渲染成rich-text如何显示文本溢出省略

uniapp 使用v-html在微信小程序中渲染成rich-text如何显示文本溢出省略

一、问题描述 小伙伴有个需求&#xff0c;想在uniapp开发的微信小程序的一个列表中对内容进行显示溢出显示省略号的控制&#xff1a;当文本超出一行之后&#xff0c;显示…。 经过尝试&#xff0c;无法在v-html所在的节点进行ellipise的控制。 二、解决方案 1.增加函数&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023