【テンプレート】文字列ハッシュ

ハッシュアルゴリズム、すなわちハッシュ関数.これは一方向暗号体制であり,すなわち明文から密文への不可逆的なマッピングであり,暗号化プロセスのみで復号化プロセスはない.同時に,ハッシュ関数は任意の長さの入力を変化させて固定長の出力を得ることができる.ハッシュ関数のこのような一方向特徴と出力データ長の固定特徴は、メッセージまたはデータを生成することができる.
純裸のテンプレート問題は文字列のハッシュ値をそれぞれ異なるようにするため,19260817(逃走)でよく見られる素数1 e 9+7,1 e 9+92331926081719660813など,奇抜な素数を取ってMODを行うことが多い.さっき、unsigned long longがオーバーフローして自動的に型を取る操作があることを知ったので、わざとカードを取らなければ、unsigned long longでやることができます.

//hash
#include 
#define MOD1 19260817
#define MOD2 19660813
#define base 133
using namespace std;
char s[1000000];
struct H{
    int one,two;
}hs[10001]; 
int hash1(char s[])
{
    int len=strlen(s);
    int ans=0;
    for(int i=0;iint)s[i])%MOD1;
    }
    return ans;
}
int hash2(char s[])
{
    int len=strlen(s);
    int ans=0;
    for(int i=0;iint)s[i])%MOD2;
    }
    return ans;
}
int comp(H a,H b)
{
    return a.oneint main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        hs[i].one=hash1(s);
        hs[i].two=hash2(s); 
    }
    int ans=1;
    sort(hs+1,hs+n+1,comp);
    for(int i=2;i<=n;i++)
        if(hs[i].one!=hs[i-1].one||hs[i].two!=hs[i-1].two)
            ans++;
    cout<return 0;
}