LeetCode3045.统计前后缀下标对II
统计字符串数组中的前缀-后缀对 —— 利用字符串哈希优化
在处理字符串相关的问题时，哈希技术常常能够提供高效的解决方案。本文将介绍一个具体的应用场景：给定一个字符串数组，统计满足特定前缀和后缀条件的字符串对的数量。我们将深入解析这个问题，并通过代码示例展示如何利用字符串哈希技术实现高效的解决方案。
问题描述
给定一个下标从 0 开始的字符串数组 words，定义一个布尔函数 isPrefixAndSuffix，它接受两个字符串参数 str1 和 str2：
- 当
str1同时是str2的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2)返回true； - 否则，返回
false。
例如：
isPrefixAndSuffix("aba", "ababa")返回true，因为"aba"既是"ababa"的前缀，也是"ababa"的后缀；isPrefixAndSuffix("abc", "abcd")返回false。
我们的目标是以整数形式返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的数量。
示例
示例 1
输入: words = ["a","aba","ababa","aa"]
输出: 4
解释: 在本示例中，计数的下标对包括：
i = 0且j = 1，因为isPrefixAndSuffix("a", "aba")为true。i = 0且j = 2，因为isPrefixAndSuffix("a", "ababa")为true。i = 0且j = 3，因为isPrefixAndSuffix("a", "aa")为true。i = 1且j = 2，因为isPrefixAndSuffix("aba", "ababa")为true。
因此，答案是 4。
示例 2
输入: words = ["pa","papa","ma","mama"]
输出: 2
解释: 在本示例中，计数的下标对包括：
i = 0且j = 1，因为isPrefixAndSuffix("pa", "papa")为true。i = 2且j = 3，因为isPrefixAndSuffix("ma", "mama")为true。
因此，答案是 2。
示例 3
输入: words = ["abab","ab"]
输出: 0
解释: 在本示例中，唯一有效的下标对是 i = 0 且 j = 1，但是 isPrefixAndSuffix("abab", "ab") 为 false。因此，答案是 0。
提示
1 <= words.length <= 10^51 <= words[i].length <= 10^5words[i]仅由小写英文字母组成。- 所有
words[i]的长度之和不超过5 * 10^5。
解决思路
这道题目考察了字符串哈希的应用，特别是如何高效地统计满足前缀和后缀条件的字符串对。我们可以通过以下步骤来解决：
- 字符串哈希基础: 将每个字符串视为一个基于某个素数（如
P = 131）的多项式表达式，并对其进行模运算（如MOD = 10^9 + 7）以计算哈希值。这样可以将字符串转换为一个唯一的数值表示，便于快速比较。 - 前缀和后缀哈希: 对于每个字符串，我们需要分别计算其所有可能的前缀和后缀的哈希值。前缀哈希可以通过从左到右累积计算，而后缀哈希则需要从右到左累积计算。
- 哈希值存储与计数: 使用一个哈希表（如
unordered_map）来存储已经计算过的前缀哈希值及其出现次数。当遍历到新的字符串时，检查其每一个前缀哈希值是否在哈希表中出现过，从而统计满足条件的字符串对。
关键代码解析
以下是实现上述思路的关键代码片段，特别是 left 和 right 哈希值的计算：
typedef long long LL;
class Solution {
public:
long long h[100010];
long long countPrefixSuffixPairs(vector<string>& words) {
unordered_map<LL,LL> mp;
int n = words.size(), P = 131, MOD = 1e9 + 7;
h[0] = 1;
long long res = 0;
for(int i = 1; i <= 100000;i ++)h[i] = (h[i-1] * P) %MOD;
for(int i = 0; i < n; i ++)
{
string s1 = words[i];
int len = s1.size();
LL left = 0, right = 0;
for(int j = 0, k = len - 1;j < len; j ++ , k --)
{
left = ( (left * P) % MOD + s1[j] ) % MOD;
right = ((s1[k] * h[j]) %MOD + right) % MOD;
if(left == right && mp[left])
{
res += mp[left];
}
}
mp[left] = mp[left] + 1;
}
return res;
}
};
left 的计算
left = ( (left * P) % MOD + s1[j] ) % MOD;
- 目的: 计算当前字符串
s1的前缀哈希值。 - 过程:
- 初始化
left = 0。 - 对于字符串中的每一个字符
s1[j]，将当前的left乘以基数P，然后加上当前字符的 ASCII 值。 - 对结果进行模运算，确保哈希值不会过大。
- 初始化
示例:
对于字符串 "abc"：
j=0:left = ('a')j=1:left = ('a' * 131 + 'b')j=2:left = (('a' * 131 + 'b') * 131 + 'c')
right 的计算
right = ((s1[k] * h[j]) % MOD + right) % MOD;
- 目的: 计算当前字符串
s1的后缀哈希值。 - 过程:
- 初始化
right = 0。 - 从字符串的末尾开始，逐个字符向前遍历（
k = len - 1到0）。 - 对于每一个字符
s1[k]，将其乘以预计算的h[j]（即P^j % MOD，其中j是当前字符在后缀中的位置），然后加上之前的right。 - 对结果进行模运算，确保哈希值不会过大。
- 初始化
示例:
对于字符串 "abc"：
j=0:right = ('c' * 1 + 0) = 'c'j=1:right = ('b' * 131 + 'c')j=2:right = ('a' * 131^2 + 'b' * 131 + 'c')
为什么 right 的计算方式这样
-
对称性:
left是从前向后累加哈希，而right是从后向前累加哈希。这样可以确保在任何时刻，前缀和后缀的哈希值能够对应起来进行比较。 -
幂次的使用:
h[j] = P^j % MOD确保每个字符在不同位置的贡献是不同的，从而减少哈希冲突。 -
模运算: 通过对
MOD取模，确保哈希值不会因为字符串过长而溢出，同时也使得哈希值分布更均匀，减少冲突。
总结
通过利用字符串哈希技术，我们能够高效地计算并比较字符串的前缀和后缀，从而快速统计满足条件的字符串对的数量。关键在于如何巧妙地计算前缀和后缀的哈希值，并通过哈希表进行快速查找和计数。这种方法不仅适用于本题，实际上在许多需要快速字符串比较的问题中，都能发挥出巨大的作用。
原文地址：https://blog.csdn.net/m0_58809631/article/details/144796777
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！