poj 1200 Crazy Search 哈希

簡單的哈希的題目   注意題目已經說明所有的nc個字符的排列組合的數不會超過16Million ,細節可以見代碼的實現

/********************* 
PRO: poj 1200 
TIT: Crazy Search 
DAT: 2013-08-30 
AUT: UKean 
EMA: [email protected] 
**********************/  
#include<cstdio>  
#include<cstring>  
#define maxn 1005  
bool has[16000006]={0};  
int asc[300],n,nc,ans=1,tag=0,base=0,chu=1,num;  
int main()  
{  
    scanf("%d %d\n",&n,&nc);  
    memset(asc,-1,sizeof(asc));  
    //初始化字符的映射表即把nc個不同的字符對映到0到nc-1這nc個數上去，  
    //這樣就可以得到nc進制的數了  
    char temp=getchar();  
    for(int i=0;i<n-1;i++)//用這個數對n位的nc進制數取模，以去掉它的最高位  
        chu*=nc;  
    for(int i=0;i<n;i++)//得到第一個n位的nc進制的數  
    {  
        num=(int)temp;  
        if(asc[num]==-1) asc[num]=tag++;  
        //按照出現的順序給nc個不同字符分別標號為0到nc-1  
        base=base*nc+asc[num];  
        temp=getchar();  
    }  
    has[base]=1;  
    while(temp!='\n')  
    {  
        int num=(int)temp;  
        if(asc[num]==-1) asc[num]=tag++;  
        //按照出現的順序給nc個不同字符分別標號為0到nc-1  
        base=(base%chu)*nc+asc[num];  
        if(!has[base])//產生了一個沒出現過的nc進制的數  
        {  
            ans++;  
            has[base]=1;  
        }  
        temp=getchar();  
    }  
    printf("%d\n",ans);  
    return 0;  
}