本文主要是介绍「字符串」字符串哈希|RK匹配：前缀哈希|滚动哈希 / LeetCode 28（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
概述
思路
核心概念：字符串哈希
算法过程
1.前缀哈希
2.滚动哈希
复杂度
Code
1.前缀哈希版
2.滚动哈希版
概述
我们今天从最简单的暴力匹配算法BF讲起，谈谈字符串哈希思想。
LeetCode 28：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 ：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
思路
最简单的暴力算法BF是最容易理解的。来看看Code。
int strStr(string haystack, string needle) {const int n=haystack.size()，m=needle.size();for(int i=0;i<n;i++){if(haystack[i]==needle[0])for(int k=i,j=0;k<n;k++){if(haystack[k]==needle[j])j++;else break;if(j==m)return i;}}return -1;}这种行为肉眼可见的愚蠢。它的时间复杂度是O(nm)，意味着在最坏情况下对于原字符串的每个字符，我们都要m次匹配。
这就是说我们总是反复的将原字符串与模式串（待寻找的字符串）进行比对。
但是我们知道只比较两个数的速度要比此快的多。
那我们能不能有一个办法，让某个数代表主串，某个数代表模式串，将这种对整个字符串的对比改造成单纯的数值上的对比呢？
核心概念：字符串哈希
哈希函数是指向其中传入一个参数，它返回一个特定的值，这个值与参数是一对一的。
字符串哈希函数就是将一个字符串转成一个整数的函数，我们期望这种转换是一对一的。这样我们可以将主串中的与模式串等长的子串依次取出，将他们转化为整数后进行快速的比对。
但一对一几乎不可能达到，凡是将某个多特征事物转化成少特征事物，总会不可避免的会发生多对一的情形，这被称为哈希碰撞或哈希冲突。但是哈希应用起来的效率极高，我们不应该抛弃这种行为，而是尽量减少冲突发生的可能。通常有双值哈希和多询问哈希等来解决，但我们在这里不会涉及。
我们知道二进制转整数是将各个位的位权*位上的数字最后求和。
1101=1*(2^3)+1*(2^2)+0*(2^1)+1*(2^0)=13
二进制 十进制我们可以将字符串也进行这样的操作，那就是将字符串当做某个进制下的整数，然后将他转换为十进制的整数。
我们通常取const int P=131。表示我们将字符串视作131进制的某个整数。溢出时通常要对一个大数取模，这里可以利用C++的无符号长整形的特点，溢出时自动对2的64次方取模。
*注意*：P不是固定的，你可以任意取得一个数作为P，但为了避免哈希冲突，一般取质数，通常是31或131或13331。
譬如有字符串“ABC”，它有前缀子串："A","AB","ABC":
//typedef unsigned long long ULL;
//#define ULL unsigned long long
using ULL = unsigned long long;
const int P = 131;
ULL hash(string str){...};string ULL //关于'A'==65详见ascii码表
hash("A") -> 65; //'A' * P^0
hash("AB") -> 8581; //'A' * P^1 + 'B' * P^0
hash("ABC")->1124178; //'A' * P^2 + 'B' * P^1 + 'C' * P^0这样，我们就得到了他的子串的哈希值，如果我们的模式串是"AB"，哈希值为8581，而主串的子串中确有8581，那么就可以快速的实现匹配。
算法过程
我们有两种手段进行匹配：前缀哈希和滚动哈希
1.前缀哈希
我们要匹配的是主串中的任意一部分，那怎么通过主串的前缀子串得到任意位置的子串呢？
观察：
hash('A') -> 65; //'A' * P^0
hash('AB') -> 8581; //'A' * P^1 + 'B' * P^0
hash('ABC')->1124178; //'A' * P^2 + 'B' * P^1 + 'C' * P^0那么我们如果想求"BC"的哈希值，就应该是：
hash('A') -> 65; //'A' * P^0
hash('ABC')->1124178; //'A' * P^2 + 'B' * P^1 + 'C' * P^0
hash('BC') -> ? //'B' * P^1 + 'C' * P^0
hash('BC') = hash('ABC') - hash('A')*P^2;我们可以定义const ULL mask= pow(P,m)，其中m是子串的长度。
前缀哈希的主要过程是前缀哈希数组的预处理。
我们有hash_main[]数组，这是主串的前缀哈希数组，表示主串到此下标时的哈希值。
那么hash_main[i]-hash_main[j]*mask就表示（j,i]的一段子串的哈希值，如果与模式串匹配成功，那么主串中的模式串起始下标是j+1。
例如，对于"ABC"，hash_main[0]=65，hash_main[1]=8581,hash_main[2]=1124178。
又有hash_pattern，表示模式串串到此下标时的哈希值。
例如，对于"BC"，hash_pattern[0]=66,hash_pattern[1]=8713。我们通常只需要最后一个数。
那么我们可以发现hash_main[2]-hash_main[0]*mask==hash_pattern[1]，这表明匹配成功了（即：主串中的某一子串与模式串哈希值完全相同）。
2.滚动哈希
滚动哈希放弃了前缀哈希数组，而利用了滑动窗口的思想。
例如，我们要匹配的模式串是"BC"，我们先求出他的哈希值=8713。
然后在主串上建立长度为m的窗口，其中m是子串的长度。
hash("AB") -> 8581; //'A' * P^1 + 'B' * P^0
hash("BC") -> 8713; //'B' * P^1 + 'C' * P^0
则hash("BC")=(hash("AB")-'A' * P^1)*P + 'C' * P^0发现哈希值与模式串相同，匹配成功。
这样一来我们就摒弃了使用O(n)级额外空间的问题，哈希值总是扔掉上一个，加入下一个数，故名滚动哈希。
复杂度
时间复杂度：O(n+m)
空间复杂度：前缀哈希：O(n+m) 滚动哈希：O(1)；
Code
*注意*：这里使用了快速幂运算求mask，你可以手写一个朴素的返回无符号长整形的pow函数，但请不要使用内置的pow函数，因为它返回的是double而不是ULL类型。
1.前缀哈希版
using ULL=unsigned long long;
const int P=131;
class Solution {
public:ULL quick_pow(ULL x,int n){ULL ans=1;while(n){if(n&1)ans*=x;x*=x; n>>=1; }return ans;}void hash(vector<ULL>& hash_map,string& str,const int len){hash_map[0]=str[0];for(int i=1;i<len;i++)hash_map[i]=hash_map[i-1]*P+str[i];}int strStr(string haystack, string needle) {const int n=haystack.size(),m=needle.size();if(m>n)return -1;vector<ULL>hash_main(n,0),hash_pattern(m,0);hash(hash_main,haystack,n);hash(hash_pattern,needle,m);if(hash_main[m-1]==hash_pattern[m-1])return 0;ULL mask =quick_pow(P,m);for(int i=m;i<n;i++){ULL hash_value=hash_main[i]-hash_main[i-m]*mask;if(hash_value==hash_pattern[m-1])return i-m+1;}return -1;}
};2.滚动哈希版
using ULL=unsigned long long;
const int P=131;
class Solution {
public:ULL quick_pow(ULL x,int n){ULL ans=1;while(n){if(n&1)ans*=x;x*=x; n>>=1; }return ans;}ULL hash(string& str,const int len){ULL ans=str[0];for(int i=1;i<len;i++)ans=ans*P+str[i];return ans;}int strStr(string haystack, string needle) {const int n=haystack.size(),m=needle.size();if(m>n)return -1;ULL main=hash(haystack,m);ULL pattern=hash(needle,m);if(main==pattern)return 0;ULL mask =quick_pow(P,m-1);for(int i=m;i<n;i++){main=(main-haystack[i-m]*mask)*P+haystack[i];if(main==pattern)return i-m+1;}return -1;}
};这篇关于「字符串」字符串哈希|RK匹配：前缀哈希|滚动哈希 / LeetCode 28（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
