字元串哈希 - POJ - 1200 字元串哈希-進制的選取

題目連結：http://poj.org/problem?id=1200

題目大意：

給你一個n和nc，以及一個字元串s，保證字元串裡出現的字元種類等于nc。

讓你求長度為n的字元串種類。

題目保證可能的字元集出現的子串最大數量不超過160萬。

思路：直接暴力把哈希值加入set，輸出st.size()，複雜度O(n*logn)，T了。

發現這個如果把nc作為進制，子串最大數量不超過160萬，那麼這個哈希值一定不會沖突并且不超過160萬。那麼就可以用vis判斷是否存在就ok了，時間複雜度O(n*nc)這題坑點就是沒有說n和nc範圍。

這個時候，防止溢出，子串不能用字首和求，字首和會爆，隻能每次求n個。

先把字元編号，然後作為nc進制求哈希值就行了。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

char s[16000010];
bool vis[16000010]={0};
int id[1010]={0};

int main()
{
    memset(id, -1, sizeof(id));
    int n, m, cut=0;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    int Len=strlen(s+1);
    for(int i=1;i<=Len;i++)
    {
        if(id[s[i]]==-1)//編号
        {
            id[s[i]]=cut++;
        }
    }

    int re=0;
    for(int i=1;i<=Len-n+1;i++)
    {
        ull ans=0;
        for(int j=i;j<i+n;j++)
        {
            ans+=ans*m+id[s[j]];
        }
        if(vis[ans]==0)
        {
            re++;
            vis[ans]=1;
        }

    }
    printf("%d\n",re);

    return 0;
}