poj 1200 Crazy Search (字符串哈希)

题目链接

题意：一个字符串，其仅由nc种字符组成，问其所有长度为n的字串里，共用多少种不同的。

思路：一开始木有懂nc种字符有什么用...

然后写了hash，发现会TLE。。。因为用到了map，被卡了个log..

nc的作用是，可以把字符串看成一个nc进制的数，这样做的好处是，得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。

然后就可以不用map而是一个数组，就变成了O(1)赋值和判断了。。。

（然而没有数据范围其实还是有点耍流氓的嫌疑。。

#include <iostream>  
#include <cstring>  
#include <stdio.h>  
using namespace std;  
const int N=16000005; //题目给出子串的最大和不超过16M  
const int NUM=257;  
bool Hash[N];  
int m[NUM];  
char str[1000000];

int n,nc,i,j,sum,seed=0,ans=0;  
int main()  
{
  //  freopen("code/in.txt","r",stdin);
    memset(Hash,false,sizeof(Hash));  
    memset(m,0,sizeof(m));  
    memset(str,'\0',sizeof(str));  
    cin>>n>>nc>>str;
    int len = strlen(str);
    for(int i = 0 ; i < len; ++i)  
    {  
        if(!m[str[i]]) //将每个字符赋值为相应进制的数  
            m[str[i]]=++seed;  
        if(seed == nc)  
            break;  
    }  
    for(i=0;i<=len-n;++i)  
    {  
        sum=0;  
        for(j=0;j<n;++j) //将字符串str[i],..,str[i+n-1]变为一个nc进制的整数,来判断是否重复出现过  
            sum=sum*nc+m[str[i+j]]-1;  
	
        if(!Hash[sum])  
        {  
            Hash[sum]=true;  
            ++ans;  
        }  
    }  
    cout<<ans<<endl;  
    return 0;  
}