Posted on 2008-10-16 15:04
歲月流逝 閱讀(197)
評論(0) 編輯 收藏 引用
字符串的算法一般大公司都會考到，我們首先要想到高效的hash。如百度查找一組字符串是否出現在某個文本中，這個不是考什么kmp，他們想聽到的是hash。趨勢科技考的是從某個文本中刪除一組字符串，我想也是要hash吧。
1 概述
鏈表查找的時間效率為O(N)，二分法為log2N，B+ Tree為log2N，但Hash鏈表查找的時間效率為O(1)。
設計高效算法往往需要使用Hash鏈表，常數級的查找速度是任何別的算法無法比擬的，Hash鏈表的構造和沖突的不同實現方法對效率當然有一定的影響，然 而Hash函數是Hash鏈表最核心的部分，本文嘗試分析一些經典軟件中使用到的字符串Hash函數在執行效率、離散性、空間利用率等方面的性能問題。
2 經典字符串Hash函數介紹
先提一個簡單的問題，如果有一個龐大的字符串數組，然后給你一個單獨的字符串，讓你從這個數組中查找是否有這個字符串并找到它，你會怎么做？有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來評價，或許它真的能工作，但...也只能如此了。最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數，通過某種算法，可以把一個字符串"壓縮" 成一個整數，這個數稱為Hash.
HDOJ-1800題目分析
除去馬甲，本題的本質是——求相同級別（level）的人最多是幾個。如果level的范圍不大的話（64位整數可以表示）——本題很簡單，簡單貪心本題的難點：level的范圍較大，需用大數或者字符串比較（去首0）效率較高、編程簡單的方法：Hash!
此外，字典樹也是不錯的選擇
http://192.168.100.16/showproblem.php?pid=1800
#include "stdio.h"
#include "memory.h"
#define MAXN 10000
inline int ELFhash(char *key)
{
unsigned long h = 0;
unsigned long g;
while( *key )
{
h =( h<< 4) + *key++;
g = h & 0xf0000000L;
if( g ) h ^= g >> 24;
h &= ~g;
}
return h;
}
int hash[MAXN],count[MAXN];
int maxit,n;
inline void hashit(char *str)
{
int k,t;
while( *str == '0' ) str++;
k = ELFhash(str);
t = k % MAXN;
while( hash[t] != k && hash[t] != -1 )
t = ( t + 5 ) % MAXN;
if( hash[t] == -1 )
count[t] = 1,hash[t] = k;
else if( ++count[t] > maxit )
maxit = count[t];
}
int main()
{
char str[100];
while(scanf("%d",&n)!=EOF)
{
memset(hash,-1,sizeof(hash));
for(maxit=1,gets(str);n>0;n--)
{
gets(str);
hashit(str);
}
printf("%d\n",maxit);
}
}