【題目來源】
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

?