淺談字元串哈希

一、引入

        雜湊演算法是通過一個哈希函數H，将一種資料（如字元串）轉化為另一種資料（通常轉化為整形數值），有些題可用map做，但資料一大就要用到字元串哈希

二、字元串哈希

        尋找長度為n的主串S中的比對串T（長度為m）出現的位置或次數屬于字元串比對問題。樸素算法（或稱為暴力）就是枚舉所有子串的起始位置，每枚舉一次就要使用O（m）的時間，總共要O（nm）的時間。當然字元串比對可以用KMP做，但這裡介紹一下字元串哈希。

        字元串哈希就是将每個字元串轉化為一個數值，然後周遊主串，判斷在主串起始位置為i長度為m的字元串的哈希值與比對串的哈希值是否相等即可，每次判斷為O(1)的時間。這樣就可以轉化為O（n）的時間完成判斷。那麼問題來了，怎麼預處理哈希值呢？

        我們選用兩個互質常數base和mod，假設比對串T=abcdefg……z（注意這裡不是指T隻有26位）那麼哈希值為              H（T）=（a*base^(m-1)+b*base^(m-2)+c*base^(m-3)+……+z）%mod。相當于把每個字元串轉換為一個base進制數，是以對于每道題我們取base時，要大于每一位上的值（避免重複），例如我們用的十進制數每一位都是小于10的。

例如字元串C="ABDB",則H（C）=‘A’+'B'*base+'D'*base^2+'B'*base^3（本人習慣直接取字元askII碼值，也可以使‘A’=1）

         那麼怎麼判斷主串起始位置為i長度為m的字元串的哈希值與比對串的哈希值是否相等呢？這裡有個公式，若求字元串中第i位到第j位的哈希值（i<j），則這個值為H(j)-H(i-1)*base^(j-i+1)。有了這個公式，我們可以預處理一個數組H[i]表示字元串從第一位到第i位的哈希值和數組power[i]表示base^i。加上判斷的時間，總時間為O（n+m）。

        在計算時，我們可以使用無符号類型（通常本人習慣使用unsigned long long）的自然溢出，這樣就可以不用%mod，包括減法也友善許多。

        當然哈希會有可能重複，base值越大重複可能性越小，本人通常取131或233317。也可使用雙哈希，即兩個不同的mod

那麼舉個栗子玩玩：Power Strings(Poj2406)

【問題描述】

      給定若幹個長度小于等于1 000 000的字元串，詢問每個字元串最多由多少個相同的子串重複連接配接而成。如：ababab最多由3個ab連接配接而成。

【輸入格式】

若幹行，每行一個字元串，遇“.”結束

【輸出格式】

每行一個數，表示最多由多少子串連成

【樣例輸入】

    abcd

    aaaa

    ababab

    .

【樣例輸出】

    1

    4

    3

【題目解析】

外循環枚舉子串長度，如果整除總長度，那麼内循環判斷，代碼如下：

#include <iostream>
#include <cstdio>
#include <cctype>
#include <climits>

using namespace std;

typedef unsigned long long ull;
const int N=1e6+5;
const ull prime=233317;//表示base 
ull power[N]={1},h[N]; 

int main()
{
    int l,i,j;
    string a;
    for(i=1;i<N;i++)  
        power[i]=power[i-1]*prime;//預處理 
    while(cin>>a)
    {
        if(a==".")
            break;
        l=a.size();
        h[0]=ull(a[0]);
        for(i=1;i<l;i++)
            h[i]=h[i-1]*prime+ull(a[i]);//預處理從第一位到第i位的hash值,自然溢出不用取模 
        for(i=1;i<=l;i++)//枚舉長度 
        {
            if(l%i)
                continue;
            bool f=1;
            for(j=i-1;j<l;j+=i)
                if(h[j]-h[j-i]*power[i]!=h[i-1])//公式 
                {
                    f=0;//不成立 
                    break;
                }
            if(f)//如果成立 
            {
                cout<<l/i<<endl;
                break;
            }
        }
    }
    return 0;
}
           

參考文獻：黃新軍等《資訊學奧賽一本通·提高篇》