C++ linux gdb c

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