字符串哈希动态规划_6

一.字符串哈希 字符串哈希概述

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

字符串哈希的结构

字符串哈希的结构包括：

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

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

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

p 是一个常数基数，通常选择一个小的质数（例如 31 或 53）。m 是模数，用于避免哈希值过大，通常选择一个大质数。s_i 是字符串中的每个字符转换为整数后的值，通常是字符的 ASCII 码或字母位置。 字符串哈希的功能 高效比较：通过哈希值，两个字符串的相等性可以通过哈希值的比较来实现，避免逐字符对比，提高效率。子串查找：通过哈希技术，快速计算任意子串的哈希值，可以用于解决许多字符串匹配的问题。避免重复：哈希值可以帮助快速去重，例如在长字符串中查找重复的子串。

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

代码实现

// 俩字符串是否相等 #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 转移方程。

一般步骤

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

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

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

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

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

状态机 DP 的经典应用 多重背包问题：通过状态来记录背包的容量和物品的状态，进行状态转移。字符串匹配：例如求解正则表达式的匹配问题，或者KMP算法的状态机。最短路径问题：特别是在有多个条件和约束的情况下，状态机可以很好地建模状态和转移。路径规划问题：比如在网格中进行路径搜索，并在状态机中管理每个路径的不同状态。 例子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]; } };