天天看點
傳回

算法學習->字元串hash一、什麼是哈希？字元串哈希有哪些？二、字元串哈希的三種映射函數三、練習題及AC代碼

一、什麼是哈希？字元串哈希有哪些？

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射pre-image）通過雜湊演算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來确定唯一的輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。

所有散列函數都有如下一個基本特性：如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有确定性的結果。但另一方面，散列函數的輸入和輸出不是一一對應的，如果兩個散列值相同，兩個輸入值很可能是相同的，但不絕對肯定二者一定相等（可能出現哈希碰撞）。

字元串hash，即把每個字元串hash為一個數字，對數字進行比對。

下面，我來示範求一個字元串的hash值：

1、要求：現在我們希望找到一個hash函數，使得每一個字元串都能夠映射到一個整數上，比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod

2、字元串：abc，bbc，aba，aadaabac，字元串下标從0開始

3、映射：先把a映射為1，b映射為2，c->3，d->4,即idx(a)=1, idx(b)=2, idx(c)=3,idx(d)=4；

4、取值：假設我們取p=13 ，mod=101

5、做法：

先把abc映射為一個整數

hash[0]=1，表示 a 映射為1（注意點）

hash[1]=(hash[0]*p+idx(b))%mod=15，表示 ab 映射為 15

hash[2]=(hash[1]*p+idx(c))%mod=97

這樣，我們就把 abc 映射為 97 這個數字了，即hash[“abc”]=97。

•用同樣的方法，我們可以把bbc，aba，aadaabac都映射到一個整數

•用同樣的hash函數，得到如下結果

• abc -> 97,即hash[“abc”]=97

• bbc -> 64,即hash[“bbc”]=64

• aba -> 95,即hash[“aba”]=95

• aadaabac -> 35,即hash[“aadaabac”]=35

•那麼，我們發現，這是一個字元串到整數的映射

•這樣子，我們就可以記錄下每個字元串對應的整數，當下一次出現了一個已經出現的字元串時，查詢整數是否出現過，就可以知道 字元串是否重複出現。

•現在要判斷兩個字元串是否一緻，怎麼辦呢？直接用它們的hash值判斷即可，若hash值一緻，則認為字元串一緻；若hash值不一緻，則認為是不同的字元串。

•我們要判斷兩個字元串是否一緻，沒有那麼麻煩，直接先判斷長度是否一緻，然後再判斷每個對應的字元是否一緻即可。

•但，如果要判斷多個字元串裡有多少個不同的字元串，怎麼辦呢？

•兩兩字元串都進行比較？時間複雜度太高

•把每個字元串hash成一個整數，然後把所有整數進行一個去重操作，即可知道答案了。

當遇到沖突時，我們可以想辦法調整p和mod，使得沖突機率減到小之又小。我們一般認為p和mod一般取素數，p取一個較大的素數即可（6位到8位），mod取一個大素數，比如1e9+7，或者1e9+9。

如何求一個子串的hash值？

•在之前，我們求出了hash[i]，表示第i個字首的hash值。現在怎麼求出每個子串的

hash值呢？

•我們看下hash的公式：

• hash[i]=(hash[i-1]*p+idx(s[i]))%mod

•這表示第 i 個字首的hash值，是一個hash的字首和。

•hash[i]=(hash[i-1]*p+idx(s[i]))%p;

•那麼，我要求S[l…r]這個子串的hash值

• hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod（假設字元串下标從1開始）

•但注意下取模時候的問題！

•hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod

• hash[l..r]是不是可能有負數？

•怎麼辦呢？當得到的hash[l..r]<0的時候，hash[l..r]+=mod，就好啦。

•這樣就可以保證每個子串的hash值在[0, mod-1]的範圍内，準确地用hash值來處理字元串

二、字元串哈希的三種映射函數

1.自動取模 

unsigned long long hash[N];
     hash[i]=hash[i-]*p（自動取模）

解釋：

unsigned long long hash[N];

定義一個unsigned long long類型的變量，它的範圍是在[0, 2^64) 内，這就相當于，當數超不過2^64-1後，它會溢出！這就相當于一個數模2^64的過程。

那麼hash函數可以了解為：

hash[i]=(hash[i-1]*p)%(2^64)

P取一個大素數，一般習慣取1e9+7或1e9+9

安全指數：三星（是以并不是很安全）

2.字元串字元 

hash[i]=(hash[i-]*p+idx(s[i]))%mod

解釋：

這個之前已經提到過了。

hash[i]=(hash[i-1]*p+idx(s[i]))%mod

p取一個6到8位的素數，mod取一個大素數，一般取1e9+7或1e9+9

安全指數：四星 （還可以）

3.雙hash 

hash1[i]=(hash1[i-]*p+idx(s[i]))%mod1
     hash2[i]=(hash2[i-]*p+idx(s[i]))%mod2
     pair<hash1,hash2>表示一個字元串！

double hash

即取兩個mod值，mod1和mod2

hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

mod1一般取1e9+7，mod2一般取1e9+9為什麼這麼取？

1000000007和1000000009是一對孿生素數，取它們，沖突的機率極低！

安全指數：五星！（非常穩！）

小結：可以這麼說，hash某種程度上就是亂搞，把hash函數弄的越沒有規律越好，使得沖突的機率小到大部分資料都卡不掉。

•如果你開心，你想triple hash，ultra hash，rampage hash… 都沒有問題！

但請注意，hash的次元越高，耗時越高，耗記憶體越大！一般情況下，single hash可以被hack掉，但double hash極難被hack掉， 用double hash足以解決問題

三、練習題及AC代碼

1、A - Crazy Search

Many people like to solve hard puzzles some of which may lead them to madness. One such puzzle could be finding a hidden prime number in a given text. Such number could be the number of different substrings of a given size that exist in the text. As you soon will discover, you really need the help of a computer and a good algorithm to solve such a puzzle.

Your task is to write a program that given the size, N, of the substring, the number of different characters that may occur in the text, NC, and the text itself, determines the number of different substrings of size N that appear in the text.

As an example, consider N=3, NC=4 and the text “daababac”. The different substrings of size 3 that can be found in this text are: “daa”; “aab”; “aba”; “bab”; “bac”. Therefore, the answer should be 5.

Input

The first line of input consists of two numbers, N and NC, separated by exactly one space. This is followed by the text where the search takes place. You may assume that the maximum number of substrings formed by the possible set of characters does not exceed 16 Millions.

Output

The program should output just an integer corresponding to the number of different substrings of size N found in the given text.

Sample Input

3 4

daababac

Sample Output

5

Hint

Huge input,scanf is recommended.

AC代碼：

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;

int has[],cnt=,vis[];
char str[];
int n,nc,ans=;

int main(){
    while(~scanf("%d%d%s",&n,&nc,str)){
        ans=;cnt=;
        int le=strlen(str);
//      memset(has,0,sizeof(has));
//      memset(vis,0,sizeof(vis));
        for(int i=;i<le;i++){
            if(vis[str[i]]==){
                vis[str[i]]=cnt++;
            }
        }
        for(int i=;i<=le-n;i++){
            int sum=;
            for(int j=;j<n;j++){
                sum=sum*cnt+vis[str[j+i]];
            }
            if(has[sum]==){
                has[sum]=;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return ;
}

2、 魔咒詞典

哈利波特在魔法學校的必修課之一就是學習魔咒。據說魔法世界有100000種不同的魔咒，哈利很難全部記住，但是為了對抗強敵，他必須在危急時刻能夠調用任何一個需要的魔咒，是以他需要你的幫助。

給你一部魔咒詞典。當哈利聽到一個魔咒時，你的程式必須告訴他那個魔咒的功能；當哈利需要某個功能但不知道該用什麼魔咒時，你的程式要替他找到相應的魔咒。如果他要的魔咒不在詞典中，就輸出“what?”

Input

首先列出詞典中不超過100000條不同的魔咒詞條，每條格式為：

[魔咒] 對應功能

其中“魔咒”和“對應功能”分别為長度不超過20和80的字元串，字元串中保證不包含字元“[”和“]”，且“]”和後面的字元串之間有且僅有一個空格。詞典最後一行以“@END@”結束，這一行不屬于詞典中的詞條。

詞典之後的一行包含正整數N（<=1000），随後是N個測試用例。每個測試用例占一行，或者給出“[魔咒]”，或者給出“對應功能”。

Output

每個測試用例的輸出占一行，輸出魔咒對應的功能，或者功能對應的魔咒。如果魔咒不在詞典中，就輸出“what?”

Sample Input

[expelliarmus] the disarming charm

[rictusempra] send a jet of silver light to hit the enemy

[tarantallegra] control the movement of one’s legs

[serpensortia] shoot a snake out of the end of one’s wand

[lumos] light the wand

[obliviate] the memory charm

[expecto patronum] send a Patronus to the dementors

[accio] the summoning charm

@END@

4

[lumos]

the summoning charm

[arha]

take me to the sky

Sample Output

light the wand

accio

what?

what?

AC代碼：

#include<stdio.h> 
#include<map>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned int ui;
const int nmax =  ;
const int INF = ;
const ui MOD1 =  + ;
const ui MOD2 =  + ;
const ui p = ;
int n, mcnt, fcnt;
char str[];
char mis[][], fun[][];
map<ui, int> mp1, mp2;

inline ui hash1(char s[]) {
    int len = strlen(s);
    ui ans = s[];
    for (int i = ; i < len; ++i) ans = ((ans * p) + s[i] ) ;
    return ans;
}
inline ui hash2(char s[]) {
    int len = strlen(s);
    ui ans = s[];
    for (int i = ; i < len; ++i) ans = ((ans * p) + s[i] ) ;
    return ans;
}
int main() {
    while (gets(str)) {
        if (str[] == '@') break;
        int len = strlen(str), pos;
        for (int i = ; i < len; ++i) if (str[i] == ']') {pos = i; str[pos] = '\0'; break;}
        strcpy(mis[mcnt], str + ); strcpy(fun[fcnt], str + pos + );
        mp1[hash1(mis[mcnt])] = fcnt;
        mp2[hash2(fun[fcnt])] = mcnt;
        fcnt++; mcnt++;
    }
    scanf("%d", &n); getchar();
    char str[];
    for (int i = ; i <= n; ++i) {
        gets(str);
        if (str[] == '[') {
            int len = strlen(str); str[len - ] = '\0';
            int ans = hash1(str + );
            if (mp1[ans] == ) printf("what?\n");
            else printf("%s\n", fun[mp1[ans]]);
        } else {
            int ans = hash2(str);
            if (mp2[ans] == ) printf("what?\n");
            else printf("%s\n", mis[mp2[ans]]);
        }
    }
    return ;
}

更多練習題：

https://vjudge.net/contest/242212#overview

解釋：以上理論講解大部分來自别的部落格，我隻是做下學習總結。

原文出自：https://www.cnblogs.com/–ZHIYUAN/p/7445842.html

哈希 字元串hash acm算法學習
上一篇: mysql 字元串的hash函數_【轉載】字元串Hash函數比較
下一篇: 性能最好的字元串轉64位Hash函數

繼續閱讀