本文共 3033 字，大约阅读时间需要 10 分钟。

1. 字符串基本操作

字符串的基本操作有读入、查找、替换、截取、数字和字符串转换等。我们常用到的方法和类有 gets(), getchar(), puts, putchar(), ..., isalpha(), isdigit(), isalnum(), ... , tolower(), toupper(), ..., sscanf(), sprintf(), atoi(), atof(), ..., stoi(), stof(), stod(), ..., to_string(), ..., getline(), ... 和 string, stringstream 类等。

下面列出了HDU的一些题目，可以做来熟悉一下字符串操作：

2. 字符串哈希

一个比较特殊的字符串匹配问题：在多个字符串中尽快操作某个字符串。如果字符串的规模很大，访问速度就非常关键。解决这个问题，最有效率的是哈希 hash 方法。用哈希函数对每个子串进行哈希，分别映射到不同的数字，即一个整数哈希值，然后就可以根据哈希值找到子串。接下来配合数据结构或者STL，完成判断重复、统计和查询等操作。

(1) 哈希函数

哈希函数是哈希方法的核心，Robin Karp 算法也是以哈希函数为最关键部分。任何函数 $f(x)$ 理论上都可以作为哈希函数，不过好的哈希函数应该尽量避免冲突，最好是没有任何冲突的完美哈希函数(或者说单射函数)——把 $n$ 个子串的 $key$ 值映射到 $m$ 个整数上，对于任意的 $ke{y}_1\ne ke{y}_2$ ，都有 $h(ke{y}_1)\ne h(ke{y}_2)$ ，此时必然有 $n\le m$ 。如果 $n=m$ ，则称为最小完美哈希函数(或者说双射函数)。

如何找到一个接近完美的哈希函数呢？事实上，已经有许多经典的字符串哈希函数，如：BKDRHash, APHash, DJBHash, JSHash, RSHash, SDBMHash, PJWHash, ELFHash 等等。当然，我们不需要全部了解。有时候，简单明了的哈希函数，其效果反而比复杂方法好得多。(这一篇文章中介绍、实现和比较了这些哈希函数)。

我们看到，BKDRHash 无论是在实际效果还是编码实现中，效果都是最突出的，因为它求得的哈希值几乎不会冲突碰撞。但是由于得到的哈希值都很大，不能直接映射到一个巨大的空间中，所以一般需要限制空间。做法求将得到的哈希值对一个设定的空间大小取余数，以余数作为索引地址，此时会产生冲突问题，也需要我们进行处理。

BKDRHash 的实现如下：

unsigned int BKDRHash(const char *str) {
         register unsigned int seed = 131, key = 0; //seed也可以取131,1313,13131,131313..    while (*str)         key = key * seed + (*str++);           //乘法分解为位运算及加减法可以提高效率,如将上式表达为:        //key = key << 7 + key << 1 + hash + ch;            //不过编译器优化后差距不大        return key & 0x7fffffff;  }

(2) 实际使用

为了实践 BKDRHash 的作用，处理实际问题中的冲突，选择一个具体例子 进行讲解。我们需要在多个字符串中尽快操作一个名为 "memory" 的子串，打印其每天的价格排名。

程序如下，用链地址法 vector<node> List[N] 来处理冲突：

#include 
   
    using namespace std;const int N = 10005;struct node {
   	char name[35];	int price;	};vector
    
      List[N];	//链地址法,用于解决冲突 unsigned BKDRHash(const char *str) {
    //哈希函数 	register unsigned seed = 31, key = 0;	while (*str) key = key * seed + (*str++);		return key & 0x7fffffff;}int main() {
   	int n, m, key, add, len, rank; //key计算哈希值,add表示每天的价格增长,rank排名 	int p[N], memory_price;		   //记录每天的所有店铺的价格, memory价格 	char str[35];	node t; 	while (~scanf("%d", &n)) {
   		for (int i = 0; i < N; ++i)			List[i].clear();		for (int i = 0; i < n; ++i) {
    			scanf("%s", t.name);			key = BKDRHash(t.name) % N;	//计算hash值并取余			List[key].push_back(t);		//hash值可能冲突,把冲突的哈希值存储起来 		}		scanf("%d", &m);		while (m--) {
   			rank = len = 0;			for (int i = 0; i < n; ++i) {
   				scanf("%d%s", &add, str);					key = BKDRHash(str) % N; //计算哈希值				for (int j = 0; j < List[key].size(); ++j) {
    //处理冲突问题 					if (strcmp(List[key][j].name, str) == 0) {
    //和输入的店铺名字一样 						List[key][j].price += add;			 //修改价格 						if (strcmp(str, "memory") == 0)		  							memory_price = List[key][j].price;						else							p[len++] = List[key][j].price;   //不是memory,记录下来 						break;								 //完成修改,直接退出 					}				}			}			for (int i = 0; i < len; ++i) 				if (memory_price < p[i])					++rank;			printf("%d\n", rank + 1);		}	}	return 0;}
    
   

(3) 其他题目

还有一些比较难的字符串哈希题目：

转载地址：https://memcpy0.blog.csdn.net/article/details/108344760 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！