字符串的算法一般大公司都會考到，我們首先要想到高效的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); } }