HDU 1800 hash 找出现最多次数的字符串的次数

乘法hash：

这类hash函数利用了乘法的不相关性

int Hash(char *str)
{
    int seed = 131 , value=0;
    while(*str != '\0'){
        value = value*seed+(*str++);
    }
    return value&0x7fffffff;
}

这里用的乘数是131 ，还推荐的乘数还有1313 ， 13131 ， 131313等

除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如：

int Hash(char *str)
{
int b = 378551 , a = 63689;

　　int hash = 0;
while(*str != '\0'){
hash = hash*a+(*str++);

　　　　a*a*b;
}
return value&0x7fffffff;
}

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 char str[];

 int _hash[];

 int Hash(char *str)

 {

     while(*str == '') str++; //这道题目的字符串要去除前导0

     int seed =  , value=;

     while(*str != '\0'){

         value = value*seed+(*str++);

     }

     return value;

 }

 int main()

 {

   //  freopen("a.in" , "r" , stdin);

     int n;

     while(~scanf("%d" , &n))

     {

         memset(_hash ,  , sizeof(_hash));

         for(int i= ; i<n ; i++)

         {

             scanf("%s" , str);

             int index = Hash(str);

           //  cout<<"index: "<<i<<" "<<index<<endl;

             _hash[i]=index;

         }

         sort(_hash , _hash+n);

         int ans = ;

         int cnt = ;

         for(int i= ; i<n ; i++){

             if(_hash[i] == _hash[i-]){

                 cnt++;

             }

             else{

                 ans = max(ans , cnt);

                 cnt = ;

             }

         }

         ans = max(ans , cnt);

         printf("%d\n" , ans);

     }

     return ;

 }

巴特西

HDU 1800 hash 找出现最多次数的字符串的次数

最新文章

热门文章