（通俗易懂小白入門）字符串Hash+map判重——暴力且優雅
- 2019 年 10 月 3 日
- 筆記
字符串Hash
今天我們要講解的是用於處理字符串匹配查重的一個算法，當我們處理一些問題如給出10000個字符串輸出其中不同的個數，或者給一個長度100000的字符串，找出其中相同的字符串有多少個（這樣描述有點不清楚但是大致的意思就是當字符串長度很長，而且涉及到多個字符串之間反覆比較時，由於比較的次數多，字符串長，很容易就超時了，而字符串Hash則是一種將字符串轉換成整數，再藉助一些STL工具如map可以很快完成查重工作）
這裡給出兩個例題輔助講解
例題一
比如有t組輸入，每次輸入n個字符串（1<=n<=10000），且字符串只有小寫字母，每個字符串長度1~10000（當然這只是個例子，也可能更長，題目也會更多變），對於這n個字符串，輸出不同的字符串的數量，（如aaa， bbb， aaa則輸出2）
例題分析
這是字符串Hash的模板題，我們要做的就是將一個個字符串轉換成整數，然後扔到map中判斷一下重複即可，而轉換的方法則是重點，在此就不得不提一下，我們所知曉的二進制（base-2），一個二進制數1010可以轉換成十進制2^3 + 2^1 == 10，而我們對於一個字符串“abab”，也可以把它當做是一個更大進制的數，如31，37，41…（因為我們通常將字符‘a’~‘z’以：單個字符 – ‘a’ 轉換成整數，而進制的選擇最好比單個整數大，且為質數更好），並且如果我們單單用：單個字符 – ‘a’ 轉換成整數則還會遇到一個問題，就是當兩個字符串“aab”和“ab”前綴相同時，由於a轉換成0，則兩個字符串轉換成的整數（以base-31為例）0*31^2 + 0*31^1 + 1*31^0 == 0*31^1 + 1*31^0將無法從數值上進行區分，就沒有達到我們需要的效果，所以我們採用：單個字符 – ‘a’ + 1的形式進行字符的轉換，這樣‘a’~‘z’則代表1~26，有效對其進行了區分
對於例題一，我們要做的就是輸入的同時，將每一個字符串轉換成一個大整數，而此時又要注意一個問題，就是當我們的字符串過長，以31進制為例，我們所塑造出的大整數很容易就超過int，long long，乃至unsigned long long的範圍，此時我們很容易想到hash的方法，就是對這個很大的整數進行MOD操作，給定一個MOD數值，這樣一個很大的數就可以被限制在一個固定區間內，但是還是會出現問題，MOD如果不夠大則很容易出現兩個大整數MOD後的值相同的情況，這裡我們希望MOD的值是一個很大數如2^64，這樣重複的進率就會很小，在這裡我們需要提及一個巧妙的技巧，對於數據類型為unsigned long long的整數，它會自動進行取模，所以不用擔心它會溢出（也省略了mod操作），所以我們用unsigned long long存放每一個字符串對於轉換成base-31後的整數，然後將這些數放入一個map映射中就可以得到不同的字符串的個數
代碼：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<string> 5 #include<map> 6 using namespace std; 7 8 typedef unsigned long long ull; 9 const int N = 10005; 10 const int base = 31; 11 12 ull operate(string s){ 13 int len = s.size(); 14 ull ans = 1; 15 for(int i = 0; i < len ; i++){ 16 ans = ans * base + s[i] - 'a' + 1; 17 } 18 return ans; 19 } 20 21 int main(){ 22 int t; 23 scanf("%d", &t); 24 map<ull, int> mp; 25 while(t--){ 26 int n; 27 scanf("%d", &n); 28 mp.clear(); 29 for(int i = 1; i <= n; i++){ 30 string s; 31 cin>>s; 32 ull sum = operate(s); 33 mp[sum]++; 34 } 35 printf("%dn", mp.size()); 36 } 37 return 0; 38 }
例題二 HDU4821 String
本題只為了藉助題干中的問題輔助講解字符串Hash，並不要求完全搞清楚題目該怎麼解，理解題意和題解核心即可，同樣是有t組輸入，每組輸入一個字符串（長度1~100000），同時輸入兩個整數m和l，求在這個字符串中，長度為m*l的子串（子串由m個長度為l的小子串拼接而成）且滿足這個子串的小子串兩兩互不完全相同（如：aab和aaa不同）
題目核心分析
對於一個字符串如abcabcbcaabc，l==3，m==3，則需要找到這個長串中長度為3*3==9的子串，且組成它的3個長度為3的小子串兩兩不完全相同，同樣的我們需要將這個長串轉換成一個進制為base的大整數同時執行MOD操作，同樣用unsigned long long作為數據存儲的類型，我們在輸入這個字符串後從下標0開始不斷求出長度為i的子串的對應的base進制的值（自動取模）存放在Hash[i]中，有點類似前綴和
1 Hash[0] = 1; 2 for(int i = 1; i < len; i++){ 3 Hash[i] = Hash[i-1] * seed + s[i] - 'a' + 1; 4 }
這裡需要注意的點是，對於一個字符串abcabc中的，前一個abc和第二個abc我們如何操作才能使得它們所代表的值是一樣的，因為字符串相同，但是出現的位置不同，如果用前綴和的形式相減得到ans = Hash[l + i – 1] – Hash[i – 1]，則由於隨着字符串的增長，越靠後的子串中字符×base的次方就越高，則ans = Hash[l + i – 1] – Hash[i – 1]當l==0和l==3時儘管它們都是對abcabc中的abc子串執行計算差的操作，後面的那個得到的ans一定會更大，所以我們需要一種方法取平衡這種由於base^n次方造成的影響，我們需要引入一個輔助數組base[]，base[i]存放base進制時base^i的值，而對於字符串abcabc，我們已經求出了下標為i時的前綴和（base進制且自動取模），ans = Hash[i + l – 1] – Hash[i – 1] * base[l]則無論子串的位置如何都能通過成base[l]將多的次方平衡掉，使得只要小子串是相同的，則差ans就是相同的，這樣我們又可以通過map進行去重操作了
由於是初步講解字符串hash操作，針對例題二的具體思路中還有一個（去頭添尾）的操作沒有講解，具體可以看代碼，也有一些注釋，而普通的做法會超時，但是出於對字符串的Hash的介紹到此已經夠了
這裡需要注意的是，在解題時你的字符串輸入後是從下標0開始還是從下標1開始的，會對ans = Hash[i + l – 1] – Hash[i – 1] * base[l]這個部分有着輕微的數值上的+1-1影響，請不要盲目照搬
代碼：
（我的這個字符串從0開始處理，會有一些邊界問題多加處理，如果從1開始則更為方便）
1 #include<set> 2 #include<map> 3 #include<stdio.h> 4 #include<string> 5 #include<string.h> 6 #include<iostream> 7 using namespace std; 8 9 typedef long long ll; 10 typedef unsigned long long ull; //自動取模？! 11 const int N = 100005; 12 const int seed = 31; 13 ull base[N]; 14 ull Hash[N]; //類似於前綴和 hash[i]存放長度為i時整個字符串代表的整數值 15 16 int main(){ 17 int m, l; 18 while(scanf("%d%d", &m, &l) != EOF){ 19 string s; 20 cin>>s; 21 int len = s.size(); 22 int ans = 0; 23 map<ull, int> mp; 24 base[0] = 1; 25 for(int i = 1; i <= l; i++) //存放seed^i的權重 26 base[i] = base[i-1] * seed; 27 Hash[0] = s[0] - 'a' + 1; 28 for(int i = 1; i < len; i++){ 29 Hash[i] = Hash[i-1] * seed + s[i] - 'a' + 1; 30 } 31 for(int i = 0; i < l && i + m*l <= len; i++){ //採用一種去頭添尾的神仙方法 32 // cout<<"LLLL"<<endl; 33 mp.clear(); 34 for(int j = i; j <= i + (m-1)*l; j += l){ 35 //每次將一個小子串代表的大數放入map中 36 if(j != 0){ 37 ull sum = Hash[j+l-1] - Hash[j-1] * base[l]; 38 // cout<<sum<<endl; 39 mp[sum]++; 40 }else{ 41 ull sum = Hash[j+l-1]; //如果是下標0開始則不需要減 42 // cout<<sum<<endl; 43 mp[sum]++; 44 } 45 } 46 // cout<<mp.size()<<endl; 47 if(mp.size() == m) ans++; 48 // cout<<"size"<<mp.size()<<endl; 49 // cout<<"mp[1]"<<mp[1]<<endl; 50 // else ans--; 51 //去頭添尾開始 52 for(int j = i + l; j + m*l <= len; j+=l){ 53 //添尾 54 ull sum = Hash[j + m*l -1] - Hash[j + (m-1)*l - 1] * base[l]; 55 // cout<<"添尾"<<endl; 56 // cout<<sum<<endl; 57 mp[sum]++; 58 // cout<<"size"<<mp.size()<<endl; 59 // cout<<"mp[1]"<<mp[1]<<endl; 60 //去頭 61 if(j-l == 0){ 62 sum = Hash[j-1]; 63 mp[sum]--; 64 if(mp[sum] == 0) mp.erase(sum); 65 // cout<<"去頭"<<endl; 66 // cout<<sum<<endl; 67 // cout<<"size"<<mp.size()<<endl; 68 }else{ 69 sum = Hash[j-1] - Hash[j-l-1] * base[l]; 70 mp[sum]--; 71 if(mp[sum] == 0) mp.erase(sum); 72 // cout<<"去頭"<<endl; 73 // cout<<sum<<endl; 74 // cout<<"size"<<mp.size()<<endl; 75 } 76 77 if(mp.size() == m) ans++; 78 } 79 } 80 if(s.size() == 1) ans=0; 81 printf("%dn", ans); 82 } 83 return 0; 84 }
