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, words) 为 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^5
[*]1 <= words.length <= 10^5
[*]words 仅由小写英文字母构成。
[*]所有 words 的长度之和不超过 5 * 10^5。
解决思绪
这道标题考察了字符串哈希的应用，特殊是如何高效地统计满足前缀和后缀条件的字符串对。我们可以通过以下步骤来解决：
[*]字符串哈希基础: 将每个字符串视为一个基于某个素数（如 P = 131）的多项式表达式，并对其进行模运算（如 MOD = 10^9 + 7）以计算哈希值。如许可以将字符串转换为一个唯一的数值表示，便于快速比较。
[*]前缀和后缀哈希: 对于每个字符串，我们必要分别计算其所有大概的前缀和后缀的哈希值。前缀哈希可以通过从左到右累积计算，而后缀哈希则必要从右到左累积计算。
[*]哈希值存储与计数: 使用一个哈希表（如 unordered_map）来存储已经计算过的前缀哈希值及其出现次数。当遍历到新的字符串时，查抄其每一个前缀哈希值是否在哈希表中出现过，从而统计满足条件的字符串对。
关键代码解析
以下是实现上述思绪的关键代码片段，特殊是 left 和 right 哈希值的计算：
typedef long long LL;
class Solution {
public:
long long h;
long long countPrefixSuffixPairs(vector<string>& words) {
unordered_map<LL,LL> mp;
int n = words.size(), P = 131, MOD = 1e9 + 7;
h = 1;
long long res = 0;
for(int i = 1; i <= 100000;i ++)h = (h * P) %MOD;
for(int i = 0; i < n; i ++)
{
string s1 = words;
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 ) % MOD;
right = ((s1 * h) %MOD + right) % MOD;
if(left == right && mp)
{
res += mp;
}
}
mp = mp + 1;
}
return res;
}
};
left 的计算
left = ( (left * P) % MOD + s1 ) % MOD;
[*]目的: 计算当前字符串 s1 的前缀哈希值。
[*]过程:
[*]初始化 left = 0。
[*]对于字符串中的每一个字符 s1，将当前的 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 * h) % MOD + right) % MOD;
[*]目的: 计算当前字符串 s1 的后缀哈希值。
[*]过程:
[*]初始化 right = 0。
[*]从字符串的末尾开始，逐个字符向前遍历（k = len - 1 到 0）。
[*]对于每一个字符 s1，将其乘以预计算的 h（即 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 = P^j % MOD 确保每个字符在不同位置的贡献是不同的，从而减少哈希冲突。
[*] 模运算: 通过对 MOD 取模，确保哈希值不会因为字符串过长而溢出，同时也使得哈希值分布更匀称，减少冲突。
总结
通过使用字符串哈希技术，我们能够高效地计算并比较字符串的前缀和后缀，从而快速统计满足条件的字符串对的数目。关键在于如何奇妙地计算前缀和后缀的哈希值，并通过哈希表进行快速查找和计数。这种方法不但实用于本题，实际上在很多必要快速字符串比较的标题中，都能发挥出巨大的作用。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]