【题目来源】
https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId=890

【题目描述】
给定一系列由大写英文字母组成的字符串关键字和素数 P，用移位法定义的散列函数 H(Key) 将关键字 Key 中的最后 3 个字符映射为整数，每个字符占 5 位；再用除留余数法将整数映射到长度为 P 的散列表中。例如将字符串 AZDEG 插入长度为 1009 的散列表中，我们首先将 26 个大写英文字母顺序映射到整数 0~25；再通过移位将其映射为 3×32^2+4×32+6=3206；然后根据表长得到3206%1009=179，即是该字符串的散列映射位置。
发生冲突时请用平方探测法解决。

【输入格式】
输入第一行首先给出两个正整数 N（≤500）和 P（≥2N 的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出 N 个字符串关键字，每个长度不超过 8 位，其间以空格分隔。

【输出格式】
在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

【输入样例1】
4 11
HELLO ANNK ZOE LOLI

【输出样例1】
3 10 4 0

【输入样例2】
6 11
LLO ANNA NNK ZOJ INNK AAA

【输出样例2】
3 0 10 9 6 1

【算法分析】
** memset‌ 函数仅适用于填充 0、-1 或特定字节模式（如 0x3f3f3f3f），其他值可能导致意外结果（如填充 1 会得到 0x01010101 而非 1）；fill‌ 函数支持任意类型的赋值（如 int、float、自定义类等），值无限制。

** 数组模拟单链表
用数组模拟单链表的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132185463

** 数组模拟散列表
用数组模拟散列表的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132179868

** 拉链法处理冲突
若数据的个数为 n，则拉链法的模 p 取大于 n 的最小素数时，处理冲突效果最好。例如，若 n=7，则 p 最好取 11 等素数。 
求大于给定数的最小素数的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132182788
拉链法常见的实现需要用数组模拟单链表实现。用数组模拟单链表的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132185463

** 开放寻址法处理冲突
若数据的个数为 n，则开放寻址法的数组空间一般开到 2n~3n，且模 p 取大于 n 的最小素数时，处理冲突效果最好。
求大于给定数的最小素数的代码详见：
https://blog.csdn.net/hnjzsyjyj/article/details/132182788

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=2e3+5;
vector<string> v(maxn);
bool st[maxn];
int n,p;int getHashVal(string str) {int t=0;int len=str.size();for(int i=max(0,len-3); i<len; i++) {t=t*32+str[i]-'A';}return t;
}int main() {cin>>n>>p;for(int i=0; i<n; i++) {string s;cin>>s;int t=-1;for(int j=0; j<p; j++) {if(v[j]==s) t=j;}if(t!=-1) {if(i!=0) cout<<" ";cout<<t;continue;}int val=getHashVal(s);int idx=val%p;int flag=0, x=0;while(st[idx]) {idx=val%p;if(!flag) {idx=(idx+x*x)%p;flag=1;} else {idx=idx-x*x;if(idx<0) idx+=p;idx=idx%p;flag=0;x++;}}v[idx]=s;st[idx]=1;if(i!=0) cout<<" ";cout<<idx;}return 0;
}/*
in:
4 11
HELLO ANNK ZOE LOLIout:
3 10 4 0
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/151638888
https://github.com/root83cn/PAT/
https://blog.csdn.net/hnjzsyjyj/article/details/132179868
https://www.acwing.com/file_system/file/content/whole/index/content/9033086/
https://blog.csdn.net/Jay_fearless/article/details/114639337